백준 7662번: 이중 우선순위 큐

문제: https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

처음에는 두개의 우선순위 큐를 사용하면 되지 않을까 했지만, 반례가 발생해서 안됐다.

그 다음 deque을 사용해야하나 했지만 우선 순위가 적용되지 않아 안됐고, 이후 map을 생각하게 됐다.

 

STL의 map은 이진 탐색 트리로 구현이 되어있으면서, begin과 end로 최댓값, 최솟값을 가져올 수 있기 때문에 적절하다고 판단했다. key가 insert되는 실제 값이고 value는 해당 값의 count다.

 

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int main() {
	int t; cin >> t;

	while (t-- > 0) {
		int k; cin >> k;

		map<int, int, greater<int>> que;

		for (int i = 0; i < k; i++) {
			char command; int value;
			cin >> command >> value;

			if (command == 'I') { // 삽입
				if (que.find(value) == que.end())
					que.insert({ value, 1 });
				else
					que[value]++;
			}
			else { // 삭제
				if (!que.empty()) {
					map<int, int, greater<int>>::iterator iter;
					if (value == 1)
						iter = que.begin(); // 최댓값
					else
						iter = --que.end(); // 최솟값

					if (--iter->second == 0) // count가 0이면 삭제
						que.erase(iter);
				}
			}
		}

		if (que.empty())
			cout << "EMPTY\n";
		else
			cout << que.begin()->first << " " << (--que.end())->first << "\n";
	}

	return 0;
}

간단하게 풀기는 했지만, 당연하다시피 속도가 매우 느렸다.

다른 사람의 코드를 보니 min-max heap이라는 자료구조가 나와 공부해봤는데, 신세계를 보았다.

Min-Max Heap: http://blog.naver.com/PostView.nhn?blogId=heojh93&logNo=220020760884

(#Tree) Min-Max Heap

 

Min-Max Heap을 구현하고 문제를 풀어보자.