문제

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


알고리즘

우선순위 큐


풀이

유명한 우선순위 큐를 활용하는 문제입니다. $N$개의 숫자들이 차례대로 주어질 때, 한 개씩 주어질 때마다 중앙값을 계속해서 출력하는 문제입니다.

여러 가지 풀이를 통해 해결 가능 하지만 우선적으로 생각나는 풀이는 트립을 활용하는 것입니다. 문제에서 요구하는 핵심 쿼리인 원소의 추가와 $k$번째 원소(여기서는 중간) 값을 찾는 쿼리를 $O(logN)$에 해결 가능하기 때문입니다.

하지만 구현이 복잡하므로 다른 풀이를 생각해보도록 합시다. 수열이 주어진 상태에서 반을 나누어 작은값부터 중간까지는 최대 힙에 중간부터 가장 큰 값까지는 최소 힙에 담도록 합시다. 이렇게 한다면 수열이 반으로 나뉜 상태긴 하지만 계속해서 정렬되어 있습니다. 원래는 정렬된 값들의 끝에만 조회가 가능한 우선순위 큐지만 이런 식으로 두 개를 나눈다면 중간값을 계속해서 조회할 수 있습니다. 더불어 아래 두 가지의 원칙을 계속 지켜나가면 됩니다.

  1. 최대 힙과 최소 힙의 크기는 같거나 최대 힙의 크기가 1 크다
  2. 항상 최대힙의 $top()$이 최소 힙의 $top()$보다 작도록 유지한다

원소의 추가와 조회에 드는 시간복잡도는시간 복잡도는 $O(logN)$이므로 최종적인 시간 복잡도는 $O(NlogN)$입니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, x;
priority_queue<int> maxpq;
priority_queue<int, vector<int>, greater<int>> minpq;

int main() {
    FAST;
    cin >> N;
    minpq.emplace(10001);
    maxpq.emplace(-10001);
    rep(i, N) {
        cin >> x;
        if (maxpq.size() == minpq.size()) maxpq.emplace(x);
        else minpq.emplace(x);

        int a = maxpq.top();maxpq.pop();
        int b = minpq.top();minpq.pop();
        if (a > b) swap(a, b);
        maxpq.emplace(a);
        minpq.emplace(b);
        cout << maxpq.top() << '\n';
    }

    return 0;
}