[백준,c++] 1655번 - 가운데를 말해요

문제

1655번: 가운데를 말해요

코드

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    priority_queue<int> left;
    priority_queue<int,vector<int>, greater<>> right;
    
    int N; cin>>N;
    for(int i=1; i<=N; i++){
        int inp; cin>>inp;
        
        if(i==1) left.push(inp);
        else if(right.empty()){
            if(left.top()<inp) right.push(inp);
            else left.push(inp);
        }
        else{
            if(inp>right.top()) right.push(inp);
            else left.push(inp);
        }
        int diff = abs((int)right.size() - (int)left.size());
        if(diff>=2){
            if(right.size()>left.size()){
                left.push(right.top());
                right.pop();
            }
            else{
                right.push(left.top());
                left.pop();
            }
        }
        
        if(i&1){    //홀수일 때
            if(right.size()>left.size()) cout<<right.top()<<'\n';
            else cout<<left.top()<<'\n';
        }
        else{   //짝수일 때
            cout<<min(left.top(), right.top())<<'\n';
        }
        
    }
}

풀이

[백준,c++] 2696번 - 중앙값 구하기

위 문제랑 상당히 유사한 문제입니다.
heap을 두 개를 사용하여 두 힙의 top 값들이 중앙값이 되어야 하기 때문에, 두 힙의 차이가 2 이상이 날 경우 사이즈가 큰 쪽의 값을 작은 쪽의 값으로 옮겨가는 아이디어로 해결하면 구현할 수 있습니다.