백준 1655번: 가운데를 말해요

문제

문제 바로가기> 백준 1655번: 가운데를 말해요

풀이

2개의 힙(최소힙과 최대힙)을 사용하여 문제를 해결했다. 최소힙과 최대힙의 개수는 최대 1 차이가 나도록 하였으며 최소힙의 모든 원소는 최대힙보다 작거나 같도록 해주었다. 이 조건을 만족하도록 두개의 힙을 만들어주면 최대힙의 top값이 정답이 된다.

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin>>n;
    priority_queue<int> maxheap, minheap;
    
    for(int i=0; i<n; i++){
        int num; cin>>num;
        if(minheap.size() < maxheap.size()) minheap.push(-num);
        else maxheap.push(num);

        if(!minheap.empty() && !maxheap.empty()){
            if (-minheap.top() < maxheap.top()){
                int maxtop = maxheap.top();
                int mintop = -minheap.top();
                maxheap.pop(); minheap.pop();
                maxheap.push(mintop); minheap.push(-maxtop);
            }
        }
        cout << maxheap.top() <<'\n';
    }
}