BOJ 1655 : 가운데를 말해요

• 문제 링크 : boj.kr/1655
• 난이도 : G2
• 태그 : 우선순위 큐

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    priority_queue<int> D;
    priority_queue<int, vector<int>, greater<int>> U;
    D.push(-INF);
    U.push(INF);
    
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        if(input < D.top()) {
            D.push(input);
            while(D.size() - 1 > U.size()) {
                U.push(D.top());
                D.pop();
            }
        }
        else {
            U.push(input);
            while(D.size() < U.size()) {
                D.push(U.top());
                U.pop();
            }
        }
        cout << D.top() << "\n";
    }

    return 0;
}

---

풀이

Min heap과 Max heap을 사용하여 현재의 중앙값보다 작은 값과 큰 값을 저장한다.

Max heap의 크기를 Min heap의 크기과 같거나 1 크도록 조절한다.

Max heap의 top이 중앙값이 된다.