가운데를 말해요 (1655)

정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다.

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

const int MAX_N = 100002;

priority_queue<int, vector<int>, less<int>> MaxHeap;
priority_queue<int, vector<int>, greater<int>> MinHeap;

int Ary[MAX_N];

/*
중간 값 구하기 알고리즘
1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.
2. 최대 힙의 최대 원소는 최소 합의 최소 원소보다 작거나 같다.
이때 알고리즘에 맞지 않다면 최대 힙, 최소 힙의 가장 위의 값을 swap해준다.
*/

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

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int Val;
        cin >> Val;

        // By 1
        if (MaxHeap.empty())
            MaxHeap.push(Val);

        else if (MaxHeap.size() == MinHeap.size())
            MaxHeap.push(Val);

        else
            MinHeap.push(Val);

        // By 2
        if (!MaxHeap.empty() && !MinHeap.empty() && !(MaxHeap.top() <= MinHeap.top()))
        {
            int a = MaxHeap.top();
            int b = MinHeap.top();

            MaxHeap.pop();
            MinHeap.pop();

            MaxHeap.push(b);
            MinHeap.push(a);
        }

        cout << MaxHeap.top() << "\\n";
    }

    return 0;
}