[백준 1655] 가운데를 말해요 (C++)

이 문제는 정수가 입력될 때마다 이미 입력된 값들 중 중앙값을 구하는 문제이다.

단순히, 벡터나 연결 리스트로 문제를 접근하면, 입력된 정수를 저장하고 정렬된 상태를 유지해야한다.
정렬 자체는 시간 복잡도가 $O(NlogN)$이므로, 정렬보다는 lower_bound로 삽입 위치를 $O(logN)$으로 알아내는 것이 더 효율적이다.

하지만, 벡터는 삽입과 삭제가 $O(N)$의 시간 복잡도를 가지고, 연결 리스트는 중앙값에 접근하는데 $O(N)$의 시간 복잡도가 필요하므로 전체 시간 복잡도는 $O(N^2)$이 되어 시간 초과가 된다.

이 문제는 스택이나 덱으로도 접근이 가능할 것처럼 보인다.

값들을 정렬했을때, 한 쪽(left)에는 중앙값의 왼쪽에 위치하는 값들을 중앙값과 함께 저장하고 다른 쪽(right)에는 중앙값의 오른쪽에 위치하는 값들을 저장한다.

즉, left.top()이 중앙값이 되도록 관리한다면, $O(1)$로 중앙값에 접근이 가능하다.

하지만, left는 증가하도록, right는 감소하도록 관리하는 것은 시간 복잡도가 $O(N)$이 된다.

왜냐하면, left나 right의 중간에 삽입되어야하는 정수가 입력되었다면, 기존에 있던 값들을 전부 빼낸 다음 다시 넣어줘야한다.

따라서, monotone-stack을 관리하는데 $O(N)$의 시간 복잡도가 핊요하며, 전체 시간 복잡도는 $O(N^2)$이 된다는 의미이다. 따라서 시간 초과가 발생하므로 선형 자료구조는 불가능함을 확인했다.

우리는 원소들이 정렬된 상태유지하면서 삽입과 삭제를 $O(logN)$이하로 진행해야 한다.

따라서, 트리형태의 자료구조가 적합하다.

아이디어는 이전에 떠올렸던 것처럼 중앙값을 포함하여 중앙값보다 왼쪽에 위치한 원소들과 중앙값의 오른쪽에 위치한 원소들을 따로 관리하도록 하고, 전자는 최대값에 바로 접근할 수 있어야하고 후자는 최소값에 바로 접근할 수 있어야한다.

이 상황에서 최대 혹은 최소만 관심을 갖게 된다. 따라서, 최대힙과 최소힙을 사용해 문제를 해결할 수 있다는 의미이다.

그렇다면, 중앙값의 왼쪽과 중앙값은 최대힙인 mx에 중앙값의 오른쪽은 최소힙인 mn에 넣어 관리하고, 매 입력마다 mx.top()을 출력해 중앙값을 출력해 줄 수 있다.

하지만, 원소가 한쪽으로 쏠리는 경우가 발생할 수 있다. 예를 들어 1 2 3 4 5나 5 4 3 2 1이 입력되면, 최대힙이나 최소힙 한 쪽으로 몰리게 된다. 이런 경우 mx.top()이 중앙값임이 보장되지 않는다.

따라서, 이에 대한 처리가 필요해지는데, 현재까지 입력된 정수의 갯수가 짝수인지 홀수인지에 따라 최대힙과 최소힙의 원소 갯수가 달라진다.

만약, 짝수라면 최대힙과 최소힙의 원소 갯수가 동일해야 mx.top()이 중앙값이 되고, 홀수라면 최대힙의 원소 갯수가 최소힙의 원소 갯수보다 1개 더 많아야 mx.top()이 중앙값이 된다.

이를 코드로 구현해보면 다음과 같이 된다.

#include <bits/stdc++.h>
using namespace std;

int n, x;
priority_queue<int> mx;
priority_queue<int, vector<int>, greater<>> mn;

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (mn.empty() || mn.top() < x) mn.push(x);
		else mx.push(x);

		if (i % 2) {
			while (mx.size() < mn.size() + 1) {
				mx.push(mn.top());
				mn.pop();
			}
			while (mx.size() > mn.size() + 1) {
				mn.push(mx.top());
				mx.pop();
			}
		} else {
			while (mx.size() < mn.size() + 1) {
				mx.push(mn.top());
				mn.pop();
			}
			while (mx.size() > mn.size() + 1) {
				mn.push(mx.top());
				mx.pop();
			}
		}

		cout << mx.top() << "\n";
	}
}