BOJ 1655: 가운데를 말해요

풀이

• 왼쪽 힙과 오른쪽 힙을 관리하면 된다.
• 그래야 가운데 값에 접근할 수 있기 때문이다.

주의

• fast io를 해야한다. 대부분의 heap 전용 문제 특징이다.
• 양쪽의 크기를 어떻게 맞추는지를 주의해야 한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    priority_queue<int> l;
    priority_queue<int,vector<int>,greater<int>> r;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x; r.push(x);
        while (not empty(l) and not empty(r) and l.top() > r.top()) {
            l.push(r.top()); r.pop();
            r.push(l.top()); l.pop();
        }
        while (size(l) < (i+1)/2) {
            l.push(r.top()); r.pop();
        }
        cout << l.top() << '\n';
    }
}