백준[1655번] 가운데를 말해요

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

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<>> minHeap;

    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;

        if (maxHeap.size() <= minHeap.size())
        {
            maxHeap.push(x);

            if (!minHeap.empty() && maxHeap.top() > minHeap.top())
            {
                int a1 = minHeap.top();
                int a2 = maxHeap.top();
                minHeap.pop();
                maxHeap.pop();
                minHeap.push(a2);
                maxHeap.push(a1);
            }
            cout << maxHeap.top() << '\n';
        }
        else
        {
            minHeap.push(x);

            if (!minHeap.empty() && maxHeap.top() > minHeap.top())
            {
                int a1 = minHeap.top();
                int a2 = maxHeap.top();
                minHeap.pop();
                maxHeap.pop();
                minHeap.push(a2);
                maxHeap.push(a1);
            }
            cout << maxHeap.top() << '\n';
        }
    }

    return 0;
}

참고: https://www.crocus.co.kr/625

1. maxheap, minheap 생성

2. maxHeap.top()이 중간값이 되도록 설정

규칙

1. maxheap.size() >= minHeap.size() : 같거나 하나 더 크다.

2. maxheap.top() <= minHeap.top(): 만약 maxHeap.top()이 minHeap.top()보다 크다면 서로 swap한다.