BOJ 1655 가운데를 말해요

Running Median Algorithm 이라고 해서, 숫자들이 들어올 때마다 실시간으로 중앙값을 출력하는 알고리즘이 있다. 

대략 설명하자면, 두 개의 힙을 유지하는데, 이 두 힙은 작은 쪽 (small) 과 큰 쪽 (big) 을 나누어 반씩 저장한다. 

단, 이때 작은 쪽은 최대 힙을 이용하여 가장 큰 원소가 위에 올라오게, 큰 쪽은 최소 힙을 이용하여 가장 작은 원소가 위에 올라오게 처리한다.

새로운 원소가 들어올 때마다 일단 작은 쪽에 넣어 보고, 필요한 개수만큼 작은 쪽의 큰 원소들을 뽑아서 큰 쪽에 집어넣어 주면 항상 원소의 개수가 같거나 작은 쪽이 1개 많게 처리해 줄 수 있다.

 

만약 지금까지 들어온 수가 짝수개라면, 두 힙에는 같은 수의 원소가 들어 있게 된다. 이때 중앙값은 정의하기 나름인데, 가운데 두 수는 각각 small 힙의 최댓값과 big 힙의 최솟값으로 둘다 top을 통해서 확인할 수 있으므로, 두 원소의 산술평균을 내든 항상 작은걸 고르든 큰걸 고르든 랜덤하게 고르든 시키는 대로 하면 된다.

 

이 문제의 경우, 두 수 중 작은 것을 중앙값으로 정의하였으므로 항상 small 힙의 최댓값을 고르기로 하자.

 

지금까지 들어온 수가 홀수개라면, small 힙에 한 개가 더 들어가게 하면 된다. (사실 아무 쪽이든 상관은 없다)

그리고 중앙값은 small 힙의 top을 뽑아내면 된다.

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

priority_queue<int> small;
priority_queue<int, vector <int>, greater<int>> big;
int main()
{
	usecppio
	int n;
	cin >> n;
	for (int i = 1; i<=n; i++)
	{
		int x;
		cin >> x;
		small.push(x);
		if (!(i%2))
		{
			big.push(small.top());
			small.pop();
		}
		while(!big.empty() && !small.empty() && (big.top()<small.top()))
		{
			int u = small.top();
			int v = big.top();
			small.pop();
			big.pop();
			small.push(v);
			big.push(u);
		}
		cout << small.top() << '\n';
	}
}