백준 C++ 1966번 프린터 큐 ( 우선순위 큐, 큐 )

하루 한 문제 나의 계획을 

오늘내일 두 개로.. 하여

끝낼 계획!

 

아직 못 푼 게 너무너무 많은데 아쉬운..

 

일단! 하나 풀어보자!

---

 

음...

그냥 그니까 큐를 쓰라는 거 같은데

 

입력을 이해하지 못했다.

 

아,

3개의 테케이고

1

환자 한 명

0 번째 환자는 언제나 오나

그 한 명의 중요도는 5

 

 

4명 있고 2번째 사람은 언제 나올까?

4명 환자의 중요도는

1 2 3 4 인 것

 

6명 있고 0번째 환자는 언제나 올까??

그 6명의 중요도는

1 1 9 1 1 1

 

인 듯하다.

 

근데 이 제보면

사람 인원수만 나와있어서..

정보를 두 개를 넣어야 한다.

 

그래서 pair을 기용할 예정이다.

 

 

 

크크크.. 오류 안 나서 막 썼는데..

답이 틀렸는데 어디가 틀린 지도 잘 모르겠다.

 

인지 씨는 3가지의 문제점을 알려주었다.

 

1. 큐를 저렇게 하나 선언해 버리면 안 된다.

3번 할 동안 새로운 큐가 필요하다!

 

2. b는 중요도인가? 번호인가?

중요도라면 second

번호라면 first 해야 하는데

b는 번호 아니던가?

 

3. 지금은 if/else 한 번밖에 안 돈다.

while문을 넣어서 큐를 다 비우든, 중요한 녀석을 찾든 해야 한다!

 

세 가지를 열심히 고쳤다.

근데도 답은 안 나온다.

 

뭔가 중요한 어떤 걸 안 한 거 같다.

 

흠.. 이제 보니

중요도에 관련되어서 아무 작동을 하지 않는다.

그냥 3번째니까 

3번째 거 뽑으려고 하고

지금 세 번째 예제처럼

0번째 걸 꺼내야 하니 1이 그냥 나오는 것이다.

하지만..

1 1 9 1 1 1 이기에

9가 먼저 나가야 하는데

이런 중요도에 관련되어선 아무런 조치를 취하지 않았다.

 

그럴 때 쓰는 친구가 있다고 한다.

 

우선순위 큐

Priority Queue

 

이 친구는

최댓값을 알려주는 검색도구라고 합니다.

 

큐는 사실

front와 back만 알 수 있는데

이 우선순위 큐는

가장 높은 값을 알려준다고 합니다.

 

 

들어간 순서와 상관없이 무조건 가장 큰 숫자를 맨 앞으로 튀어나오게 하는

강력한 특징을 가지고 있어서

 

이 친구를 함께 사용해야 한다고 합니다.

 

priority_queue <int> pq;라고 지어주겠습니다.

 

 

 

처음에 중요한 값을

같이 우선순위 큐에도 넣어주었습니다.

 

 

 

중요한 건 여기 식!

q가 empty일 때까지 계속 굴려주도록 whlie문을 구성하고

 

pair를 통해 값을 두 개 넣었으니

변수로 만들어주고 ( 쉽게 보기 위해 )

값을 넣어주었으니

 

q를 pop 해준다.

만약에 위에서 해주지 않았다면?

 

첫 번째 else문에서도 pop를 해줘야 하고

맨 밑에 else에서도 pop를 따로 해줘야 한다.

왜? 그래야 다음으로 넘어가기 때문

 

그래서 값을 이미 변수로 저장해 두었으니

그래서 처음부터 빼주고 시작하면 좀 더 편해서 빼주게 된다.

 

if문에서는

만약에 중요도가 높은 사람이 지금 맨 앞에 있는 사람이다!

 

하면 우선순위 높은 것을 빼주고

그다음에 몇 번째인지도 확인해 주어야겠죠!

만약에 내가 찾던 번호다 하면

출력 후 break 

아니면 cnt++ 올려주기

 

 

그리고 중요도가 다르면

그냥 맨 앞에서 빼놨던 거 다시 맨뒤로 넣어줘서 한 바퀴 돌리기

 

말로 하니깐 좀 어려운데...

성공은 했습니다.

...

 

---

 

중요한 건

1. pair로 만들어서 숫자 두 개 넣기

 

2. 큐랑 우선순위 큐 둘 다 쓰기

queue

priority_queue

 

3. while문! q.empty 해줘서 루프 돌리기

pop 잘 빼주기

 

다음에 똑같은 문제를 또 잘 풀어낼 수 있을까?

자신이 없다.. 엄청 어렵다 단어도 어렵다 다 어렵다

엄청 어렵다.

엄청 엄청 어렵다.