[BOJ] 1655: 가운데를 말해요

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

1655번: 가운데를 말해요

 

 

정렬을 통해서 푸는 방법은 $O(N^{2}\log(N))$의 시간 복잡도가 필요하니 제한 시간에 걸려 풀 수 없고, 나는 최소 힙과 최대 힙을 통해 풀었다.

 

최대 힙으로 구현된 left, 최대 힙으로 구현된 right 변수를 각각 만들어준다.

어떤 정수 n이 입력으로 들어올 때, left에 있는 원소 중 최댓값(최대 힙으로 구현되어 있으니 $O(\log(N))$의 시간복잡도로 구할 수 있다)과 n을 비교한다.

 

그 이후로는 left의 최댓값보다 n이 작다면 left에, 아니라면 right에 추가한다.

 

n을 추가한 후 left와 right의 크기가 같아지게끔 left/right에 있는 원소를 다른 힙으로 옮긴다.

원소의 수가 홀수일 경우 크기가 같아질 수 없으므로 left의 크기가 right의 크기보다 크게끔 설정한다.

 

문제에서 짝수일 때는 더 작은 수를 말하므로 이 경우 left의 최댓값을 출력하면 항상 문제의 조건을 만족한다.

홀수일 때 또한 left의 크기가 right의 크기보다 크므로 left의 최댓값은 현재까지 말한 모든 수의 중간값이다.

 

최대/최소 힙을 직접 구현해도 되지만, STL에 구현되어 있는 우선순위 큐를 사용해도 별 문제는 없다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

	priority_queue<int, vector<int>, less<int>> left;
	priority_queue<int, vector<int>, greater<int>> right;
	constexpr char NewLine = '\n';

	int n; cin >> n;

	while (n--) {
		int num; cin >> num;
		if (left.empty() || right.empty())
			left.push(num);
		else if (num <= left.top())
			left.push(num);
		else
			right.push(num);

		while (left.size() != right.size() && (left.size() != right.size() + 1)) {
			if (left.size() > right.size()) {
				right.push(left.top());
				left.pop();
			}
			else {
				left.push(right.top());
				right.pop();
			}
		}

		cout << left.top() << NewLine;
	}

	return 0;
}