취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2696번 문제인 중앙값 구하기이다.
문제는 아래 링크를 확인하자.

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

2k-1개의 수를 지금까지 읽었을 때 각 수들은 (중앙값 이하의 k-1개의 수), 중앙값, (중앙값 이상의 k-1개의 수)와 같이 들고 관리하고 있을 수 있다.

이 상태에서 두 개의 수가 더 추가될 때, 두 수중 하나는 중앙값 이하이고 하나는 중앙값 이상이라면 각 값을 중앙값 이하의 수의 모임과 이상의 수의 모임에 집어넣어 위의 형태를 유지할 수 있다.

두 값이 모두 중앙값 이상인 경우, 현재의 중앙값을 중앙값 이하의 수의 모임으로 옮기고 두 값과 중앙값 이상의 k-1개의 수 중 가장 작은 수를 중앙값으로 한 뒤 남은 수를 중앙값 이상의 수의 모임으로 하면 위의 형태를 유지할 수 있다. 이는 두 값이 모두 중앙값 이하인 경우에도 비슷하게 적용할 수 있다.

위와 같은 관리를 효율적으로 하기 위해 우선순위 큐(priority queue) 자료구조를 이용할 수 있다. 이를 이용해 문제를 해결하자.

int형을 관리하는 우선순위 큐에 각 수를 음의 부호를 붙여 max heap을 min heap처럼 이용할 경우 -2^31에 음의 부호를 붙이면 코드가 의도대로 작동하지 않을 수 있음에 유의하자. (-2^31은 int형의 범위에 포함되지만, 2^31은 int형이 표현할 수 있는 범위에 포함되지 않는다는 점을 상기하자.)

또한, 문제의 답을 출력할 때 정수를 10개 단위로 끊어서 출력해야함에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;

void solve() {
	
	int N; cin >> N;
	cout << N / 2 + 1 << '\n';
	ll mid; cin >> mid;
	cout << mid << ' ';
	priority_queue<ll> L, R;
	N >>= 1;
	int cnt = 1;
	while (N--) {
		ll x, y; cin >> x >> y;
		if (x > y) swap(x, y);
		
		if (y <= mid) {
			R.push(-mid);
			L.push(x); L.push(y);
			mid = L.top(); L.pop();
		}
		else if (mid <= x) {
			L.push(mid);
			R.push(-x); R.push(-y);
			mid = -R.top(); R.pop();
		}
		else L.push(x), R.push(-y);

		if (cnt == 10) cnt = 0, cout << '\n';
		cout << mid << ' ';
		cnt++;
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) solve();
}