[Baekjoon] 7662번: 이중 우선순위 큐

🥅 문제

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

 

🔍 설계

처음에 min_pq와 max_pq만을 만들어서 D일 때 n이 무엇이냐에 따라 한쪽으로 몰아서 처리하는 방식을 택했는데 시간 초과가 발생했다. 다른 방법을 찾아야 한다.

 

map을 이용하여 개수를 저장하고, D일 때, 삭제를 하기 전, 다른 명령에서 개수가 0이 되었을 수도 있으므로 그 경우를 고려하여 삭제 처리를 해주어야 한다. 예를 들어 D 1이어서 max_pq에서는 삭제했지만, min_pq에서는 삭제할 수 없으므로 반영되지 않았다. 개수만 감소시키고, 삭제하려는 수의 개수가 0일 때, 모두 삭제한다.

 

👊 풀이

#include <iostream>
#include <queue>
#include <map>
using namespace std;

char ch;
int t, k, n;

int main(void)
{	
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> k;
		priority_queue<int, vector<int>, greater<int>> min_pq;
		priority_queue<int> max_pq;
		map<int, int> save;
		for (int j = 0; j < k; j++) {
			cin >> ch >> n;
			if (ch == 'I') {
				min_pq.push(n);
				max_pq.push(n);
				if (save.count(n) == 0){
					save[n] = 1;
				}
				else{
					save[n] += 1;
				}
			}
			else {
				if (n == 1) {
					while (!max_pq.empty() && save[max_pq.top()] == 0){
						max_pq.pop();
					}
					if (!max_pq.empty()){
						save[max_pq.top()] -= 1;
						max_pq.pop();
					}
				}
				else {
					while (!min_pq.empty() && save[min_pq.top()] == 0){
						min_pq.pop();
					}
					if (!min_pq.empty()){
						save[min_pq.top()] -= 1;
						min_pq.pop();
					}
				}
			}
		}
		while (!max_pq.empty() && save[max_pq.top()] == 0){
			max_pq.pop();
		}
		while (!min_pq.empty() && save[min_pq.top()] == 0){
			min_pq.pop();
		}
		if (max_pq.empty() && min_pq.empty()){
			cout << "EMPTY" << "\n";
		}
		else{
			cout << max_pq.top() << " " << min_pq.top() << "\n";
		}
	}
	return 0;
}