백준 1655 - 가운데를 말해요, C++, 우선순위 큐

1655번: 가운데를 말해요

#include <iostream>
#include <queue>
using namespace std;

int n, input;

// smallerQ.top() < biggerQ.top();
priority_queue<int> biggerQ;    // max-heap
priority_queue<int> smallerQ;   // min-heap

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> input;
        if(biggerQ.size() > smallerQ.size())
            smallerQ.push(-input);
        else 
            biggerQ.push(input);

        if(!biggerQ.empty() && !smallerQ.empty()){
            if(-smallerQ.top() < biggerQ.top()){
                int small = -smallerQ.top();
                int big = biggerQ.top();

                smallerQ.pop();
                biggerQ.pop();

                biggerQ.push(small);
                smallerQ.push(-big);
            }
        }


        // biggerQ >= smallerQ
        cout << biggerQ.top() << '\n';
    }
}

---

우선순위 큐 2개만 있으면 쉽게 풀이할 수 있는 문제였습니다. 그 2개가 위에 있는 최대 힙, 최소 힙으로

 

- 최대 힙에는 최소힙보다 0~1 크기가 더 크다

- (최소 힙의 top) > (최대 힙의 top)이 되도록 유지해 준다

    - 이 규칙은 매번 input이 있을때 각 힙의 top을 비교해 교체해주면 됩니다.

 

위 코드에서는 greater을 따로 만들지 않아 큐에 넣을떄 최소 힙에는 -를 붙여서 구현을 했습니다.