c++ priority queue 예제 : compare 구조체만 잘 정의합시다.

 priority_queue는 코딩 테스트에서 꽤 빈도 높게 출제되고 있는 자료 구조 중 하나입니다. 물론, set이나 map도 많이 보이긴 합니다. 여태까지 코딩 테스트 문제들을 쭉 보았을 때, 우선 순위 큐, 줄여서 pq를 사용해서 푸는 문제가 꽤 많이 등장하였습니다. 자료구조나, 알고리즘 시간에 반드시 한 번 쯤은 짚고 넘어가는 것을 물어보았다는 것은, 기본을 보았다는 소리입니다.

 

 이것은 한 마디로 top 메서드를 호출했을 때, 우선 순위가 가장 높은 것을 꺼내는 구조입니다. 그것이 전부입니다. 하지만, 그러한 작업과, 삽입, 삭제가 O(log)가 보장됩니다. 왜 그런지는 자료 구조 시간에 다시 언급해 드리도록 하겠습니다. 일단, 오늘은 log라는 것만 머릿속에 넣으시면 되겠습니다.

 

 

---

 보통 저는 pq를 쓸 때, 아래와 같이 많이 씁니다.

 

 

priority_queue <T,vector<T>,compare> pq;

 

 

 T는 구조체를 의미합니다. 예를 들어서 struct moo와 같은 것을 의미합니다. 2번째 인자는 보통 vector <T>와 같이 default로 넣는다고 보시면 됩니다. 3번째로 표시한 compare가 문제인데요. 우선 순위를 어떻게 정하느냐를 정의한 구조체를 의미합니다. 예를 들자면, 좌표를 저장하고 있는 구조체 point가 있습니다. 우선 순위가 어느 쪽이 제일 높아야 할까요? 이런 것을 정해야 하는데, compare가 그러한 역할을 합니다. 우리는 이 구조체를 정의해야 합니다. 사실 그 작업이 90%입니다. 예제 프로그램을 보면서 차근 차근 이해해 보도록 하겠습니다.

 

 

 먼저 moo 구조체에 필드 x, y가 있습니다.

 

 

 우리는 moo의 우선 순위를 재정의하는, compare 구조체를 정의할 건데요. operator() 메서드를 재정의를 할 겁니다. moo의 우선 순위를 재정의 하기 때문에, 인자를 2개 받습니다. moo &I와, moo &C. 이렇게 2개의 대상체를 받습니다. 그것 외에 나머지는 sort 함수의 compare 정의하듯 하면 된다는 것을 알 수 있습니다.

 

 I와 C를 각각 1번째 인자, 2번째 인자로 넘겼을 때, I.x < C.x이거나, I.x와 C.x가 같으면서 I.y<C.y라면 true를 리턴하는데요.

 

 

 main 함수를 보도록 하겠습니다. 보시면, 좌표를 입력을 받고, pq에 n개의 데이터를 넣습니다. 그리고 우선 순위 큐에서, 계속 아이템을 빼면서, 출력하고 있음을 알 수 있는데요.

 

 

 실행 결과는 위와 같이 나옵니다. x가 큰 것부터, x가 같다면 y가 큰 순서대로 나온다는 것을 알 수 있어요. sort 함수에서 cmp 함수를 재정의 할 때와 반대의 상황이 나온다는 것을 알 수 있는데요. 그러면 실제로 x가 작은 게 먼저, x가 같다면, y가 작은 게 먼저 나오게 하려면 어떻게 compare 구조체를 바꿔야 할까요?

 

 

 이렇게 바꾸면 됩니다. C의 우선순위가 더 높다면 true를, 아니라면 false를 리턴해야 하는데요. 그럴려면 C.x < I.x이거나, C.x와 I.x가 같으면서 C.y < I.y이면 됩니다.

 

 

 그러면, x가 낮은 순서대로, x가 같다면 y가 낮은 순서대로 잘 나온다는 것을 알 수 있어요. 일반적인 sort 기준하고는 거꾸로 갑니다. 즉, compare 구조체에서, bool operator()를 재정의 했을 때, 2번째 인자의 우선 순위가 더 높다면 true를 리턴하고, 그렇지 않다면 false를 리턴하면 된다는 것입니다.

 

 

---

 조금 어려운 예제를 봅시다. 이번에는, 나이와 이름이 있습니다. 당연하게도 이름은 소문자만으로만 이루어져 있습니다. 이 때, 우리는 나이가 적은 사람이 우선 순위가 높게 하고 싶어요. 만약에 나이가 같은 사람이 여럿이라면, 사전 순으로 앞에 있는 사람의 priority가 높게 하고 싶어요. 어떻게 하면 될까요?

 

 

 moo 구조체는 위와 같습니다. 각각 나이와 이름을 저장하고 있습니다. compare 구조체를 재정의 할 건데요.

 

 

 2번째 인자인 C의 우선순위가 더 높아야 합니다. 우선순위가 높아야 할 조건은 age가 작아야 합니다. 만약에 I.age와 C.age가 같지 않다면, C.age는 I.age보다 작아야 합니다. 그런데, 14번째 줄에 걸리지 않으면, 어떻게 해야 할까요? 이 때에는 C.str이 I.str보다 사전 순으로 앞서야 합니다. 그럴려면 strcmp(C.name,I.name)이 0보다 작아야 할 겁니다.

 

 

 이렇게 compare 구조체를 작성해 주시면 됩니다.

 

 

 그러면 요구한 조건에 맞게 pq에 들어가고 빠진다는 것을 알 수 있어요. 이것만 잘 정의하면, 90%는 끝났다고 보셔도 됩니다.

 

 

---

 이제, pq에서 많이 쓰는 4대장만 언급하고 마치겠습니다.

 

 

우선순위 큐에서 가장 많이 쓰는 4개의 메서드