백준 [7662] "이중 우선순위 큐"

이중 우선순위 큐문제는 문제 이름에서 알 수 있듯이 우선순위 큐를 이중으로 사용해서 해결하는 문제이다. 우선 순위 큐를 두개를 이용해야 한다는걸 알 수는 있었지만 문제를 해결하고자 할때 "왜 두개를 사용하지? 그냥 하나로 해도 충분할거 같은데" 라는 안일한 생각을 가지고 문제를 해결하고자 하였다.

하지만 이중 우선순위큐를 사용함에 있어서 최대값과 최소값을 동시에 제어하기에는 상당히 큰 자원이 소모됐고 결국 우선순위 큐를 두개를 사용하게 되었다.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <map>

using namespace std;
int T;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> T;

	for (int j = 0; j < T; j++) {
		priority_queue<int, vector<int>, greater<int>> min_queue;
		priority_queue<int, vector<int>, less<int>> max_queue;
		map<int, int> cnt;
		int k;
		cin >> k;
		for (int i = 0; i < k; i++) {
			string DI;
			int n;
			cin >> DI >> n;
			if (DI == "I") {
				min_queue.push(n);
				max_queue.push(n);
				cnt[n]++;
			}
			else if (DI == "D") {
				if (n == 1 && !max_queue.empty()) {
					cnt[max_queue.top()]--;
					max_queue.pop();
				}
				else if (n == -1 && !min_queue.empty()) {
					cnt[min_queue.top()]--;
					min_queue.pop();
				}
			}
			while (!min_queue.empty() && cnt[min_queue.top()] == 0) {
				min_queue.pop();
			}

			while (!max_queue.empty() && cnt[max_queue.top()] == 0) {
				max_queue.pop();
			}
		}
		if (max_queue.empty() || min_queue.empty()) {
			cout << "EMPTY" << "\n";
		}
		else {
			cout << max_queue.top() << " " << min_queue.top() << "\n";
		}
	}
	return 0;

}