Baekjoon 1655번 가운데를 말해요

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, x;
priority_queue<int> l, r;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    // 1번째
    cin >> x;
    l.push(x);
    cout << l.top() << "\n";
    // 2번째
    cin >> x;
    if(x >= l.top()){
        r.push(-x);
    }
    else{
        r.push(-l.top());
        l.pop();
        l.push(x);
    }
    cout << min(l.top(), -r.top()) << "\n";
    // 3~n 번째
    for(int i = 3; i <= n; i++){
        cin >> x;
        if(i%2 == 0){ // 짝수번째, 짝수개
            if(x >= l.top()){
                r.push(-x);
            }
            else{
                r.push(-l.top());
                l.pop();
                l.push(x);
            }
            cout << min(l.top(), -r.top()) << "\n";
        }
        else{
            if(x <= -r.top()){
                l.push(x);
            }
            else{
                l.push(-r.top());
                r.pop();
                r.push(-x);
            }
            cout << l.top() << "\n";
        }
    }
    return 0;
}

이 문제는 두개의 힙을 사용하면 해결할 수 있다.

왼쪽이 최대힙 오른쪽이 최소힙 일 때 왼쪽부터 번갈아가며 숫자를 채워 나간다.

두 힙의 크기가 균형을 이루며 모든 값이 오름차순일 경우, 숫자의 총 개수가 홀수면 최대힙의 top, 짝수면 두 힙의 top 중 작은 값 이 중간값이 된다.

힙에 값이 올바르게 들어가려면 각 차례마다 반대편 힙의 top 원소와 외친 수를 비교하여 어느 힙에 숫자를 삽입해야 하는지 확인하는 과정이 필요하다.