[C++] 백준 7662번 : 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

---

 문제풀이

멀티셋, 우선순위 큐로 풀 수 있는 문제이다.

명령어는 두 가지로 우선순위 큐에 값을 집어넣는 'I'와 값을 pop 하는 'D'가 있다.

우선순위 큐를 통해서 구현했기 때문에 각각 maxheap, minheap으로 구현했다. (내림차순, 오름차순)

큐가 두개라서 값을 pop 할 때 두 개의 큐에서 모두 처리가 돼야 하기 때문에 상태를 나타내는 배열을 추가했다.

'I' 명령어는 단순하게 value를 각 큐에 추가해주면 된다.

'D' 명령어는 큐가 비어있다면 해당 작업을 무시해주고 비어있지않다면 큐의 top의 상태를 확인해서 pop 해준다.

top의 상태를 확인하는 이유는 minheap에선 삭제했는데, maxheap에선 아직 처리가 되지 않았을 수 있기 때문이다.

반복이 끝나면 한번 더 추가적으로 top의 상태를 확인해주고 조건에 따라 출력한다.

 느낀 점

멀티셋으로 구현한다면 쉬운 문제였다. 하지만 우선순위 큐를 이용해서 구현하여 더 우선순위 큐와 힙에 대한 이해도가 올라갔다!!

 코드

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

using namespace std;

int n, t;
bool is_used[1000001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		priority_queue<pair<int, int>> pq1; // max
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq2; // min
		cin >> t;
		for (int j = 0; j < t; j++) {
			int n;
			char cmd;
			cin >> cmd >> n;
			if (cmd == 'I') {
				pq1.push({ n, j });
				pq2.push({ n, j });
				is_used[j] = true;
			}
			else {
				if (n == 1) {
					while (!pq1.empty() && !is_used[pq1.top().second])
						pq1.pop();
					if (!pq1.empty()) {
						is_used[pq1.top().second] = false;
						pq1.pop();
					}
				}
				else {
					while (!pq2.empty() && !is_used[pq2.top().second])
						pq2.pop();
					if (!pq2.empty()) {
						is_used[pq2.top().second] = false;
						pq2.pop();
					}
				}
			}
		}
		while (!pq1.empty() && !is_used[pq1.top().second])
			pq1.pop();
		while (!pq2.empty() && !is_used[pq2.top().second])
			pq2.pop();

		if (pq1.empty() && pq2.empty()) 
			cout << "EMPTY" << "\n";
		else 
			cout << pq1.top().first << " " << pq2.top().first << "\n";
	}
}