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

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

1655번: 가운데를 말해요

 

문제 이해는 쉬운데 어떻게 해야할지 감이 안잡히는 문제이다. 

게다가 제한시간이 무려 0.1초다. 무조건 O(N)으로 풀어내야한다.

아이디어는 다음과 같다.

 

1 2 3 4 5 가 있다고 하자 그렇다면 여기서 1,2,3 은 최대힙 4,5는 최소힙으로 구성한다. 

그렇다면 언제나 최대힙의 top이 정답이된다. 

이것이 가능하려면 여기서 규칙이 생긴다.

1. 최대힙의 개수는 언제나 최소힙과 같거나 1개가 크다. 왜냐하면 최대힙의 top이 정답으로 나와야하기 때문이다.

2. 최대힙의 top은 언제나 최소힙의 top보다 작다. 그래야 전체가 오름차순이 유지된다.

 

1 2 3 이

 

1 -> 1번 규칙에 의해 최대힙에 1 푸쉬

2 -> 2번 규칙에 의해 최소힙에 2 푸쉬

3 -> 1번 규칙에 의해 최대힙에 3 푸쉬 그런데, 최대힙의 top = 3 최소힙의 top = 2 이므로 2번에 위배되므로 둘을 swap 

 

정답코드는 다음과 같다.

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	int N;
	cin >> N;
	int tmp;
	cin >> tmp;

	vector<int> answer;

	max_heap.push(tmp);

	answer.push_back(tmp);

	for (int i = 1; i < N; i++) {
		cin >> tmp;
		if (max_heap.size() == min_heap.size())
			max_heap.push(tmp);
		else
			min_heap.push(tmp);

		if (max_heap.top() > min_heap.top()) {
			int M_h = max_heap.top();
			int m_h = min_heap.top();

			max_heap.pop();
			min_heap.pop();

			max_heap.push(m_h);
			min_heap.push(M_h);
		}

		answer.push_back(max_heap.top());
	}

	for (auto a : answer)
		cout << a << '\n';
}