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

https://www.acmicpc.net/problem/1655

주어지는 입력을 소트한다고 했을 때, 그 중간 값을 뽑아내며, 

전체 짝수가 주어지면 중간 값 2개 중 더 작은 애를 뽑아내는 문제다.

이 문제를 해결하는 방법을 생각해보자.

먼저 드는 생각은 balanced tree를 만들어 중간 위치를 찾으면 그만이다.

하지만, treap이나 red-black tree를 어느 세월에 만들어 낼 것인가....

문제의 유형처럼 heap으로 해결해보자.

heap으로 해결하는 방법이 선뜻 떠오르지 않는다.

먼저 2개의 heap을 만들어 낸다.

maxHeap과 minHeap인데

주어진 수열을 sort한 다음, 앞 절반을 maxHeap에,  뒷 절반을 minHeap에 넣으면 

다음 2가지 성질이 성립된다.

1. maxHeap의 size는 minHeap size보다 같거나 1크다.

2. maxHeap의 첫 원소는 minHeap의 첫 원소보다 작거나 같다.

자 input이 주어지면, 

input을 maxHeap, minHeap 번갈아서 넣는다. maxHeap 먼저.

그리고 maxHeap의 첫 원소와 minHeap의 첫 원소를 비교해서

maxHeap이 더 크면, 2개의 위치를 바꾸어준다.

#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    int n; scanf("%d", &n);
    priority_queue<int> maxHeap, minHeap;
    
    for (int i = 0; i < n; i++) {
        int inp; scanf("%d", &inp);
    
        if (maxHeap.size() == minHeap.size()) {
            maxHeap.push(inp);
        }
        else {
            minHeap.push(-inp);
        }
        if (!minHeap.empty() && !maxHeap.empty() && -minHeap.top() < maxHeap.top()) {
            int a = maxHeap.top(), b = -minHeap.top();
            maxHeap.pop(), minHeap.pop();
            maxHeap.push(b);
            minHeap.push(-a);
        }
        printf("%d\n", maxHeap.top());
    }
    return 0;
}