Baekjoon 1655 (가운데를 말해요)

Baekjoon 1655, 백준 1655 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <queue>

using namespace std;

int main() {
    int N;
    // make two priority queues: max and min
    // max_pq is less<int>, min_pq is greater<int>
    // every numbers in min_pq are bigger than every numbers in max_pq
    // every time, max_pq.size() should be same or 1 bigger than min_pq.size()
    priority_queue<int, vector<int>, less<int>> max_pq;
    priority_queue<int, vector<int>, greater<int>> min_pq;

    scanf("%d",&N);

    while(N--) {
        // get input
        int num;
        scanf("%d", &num);

        // push num
        if(max_pq.size() == min_pq.size()) {
            max_pq.push(num);
        }

        else min_pq.push(num);

        // sort
        if(!min_pq.empty() && max_pq.top() > min_pq.top()) {
            // swap the two top values
            int min_temp = min_pq.top();
            int max_temp = max_pq.top();
            min_pq.pop();
            max_pq.pop();
            min_pq.push(max_temp);
            max_pq.push(min_temp);
        }

        // print middle value: top of max_pq
        printf("%d\n", max_pq.top());
    }
}

Priority Queue 하나로는 해결할 수 없었다.
<queue>의 경우에는 정렬이 잘 되어 있다 한들, 직접 index로 참조할 수 있는 방법이 없기 때문이다.
( top 과 back 만 값을 읽어올 수 있다. 중간 값 못 읽어온다 )

직접 배열로 Heap을 만들어서도 해결할 수 없다.
Heap의 경우 배열 자체가 정확히 오름차순 정렬이 된 것이 아니기 때문이다.
( 예로, heap[3] > heap[4] 를 보장할 수 없다 )

본 문제는 Priority Queue 두 개를 사용하는 것이 일반적인 풀이였다.
min_pq, max_pq 의 두 개의 Queue를 사용하여
가운데 값이 max_pq의 top이 되도록 하였다!

필자는 두 개의 Queue를 사용하라는 힌트를 듣고 아하! 하고 바로 해결하였다.
굉장히 간단하면서도 인상적인 알고리즘이었다.