[자료구조] 백준 7662번: 이중 우선순위 큐 (C++), 두 큐를 하나처럼, 싱크의 핵심

입력값을 넣을 때마다 즉각적으로 정렬을 시키면 되는 문제가 아닐까를 생각했지만 정렬의 시간 복잡도 O(NlogN), 연산의 최대 개수가 1,000,000이므로 이는 시간 초과를 발생시킨다.

즉, 이번 문제에서는 우선순위 큐(priority queue)의 사용을 유도한다.

큐의 특성상 pop(D)를 할 때는 앞에서 밖에 할 수 없기 때문에 두 개의 우선순위 큐를 선언해주었다.

오름차순과 내림차순.

두 개의 큐를 선언하여 풀었던 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int n;
		cin >> n;
		priority_queue<ll> q; // 내림차순
		priority_queue<ll, vector<ll>, greater<ll>> q2; // 오름차순
		int cnt = 0;
		for (int j = 0; j < n; j++) {
			char idx;
			cin >> idx;
			if (idx == 'I') {
				ll value;
				cin >> value;
				q.push(value);
				q2.push(value);
				cnt++;
			}
			else if (idx == 'D') {
				ll value;
				cin >> value;
				if (!q.empty() && value == 1) {
					q.pop();
					cnt--;
				}
				else if (!q2.empty() && value == -1) {
					q2.pop();
					cnt--;
				}
			}
		}

		if (cnt > 0) {
			cout << q.top() << ' ' << q2.top() << '\n';
		}
		else {
			cout << "EMPTY" << '\n';
		}
	}
	return 0;
}

cnt를 이용하여 큐가 비었는지 확인을 해주며 출력을 했다.

하지만, 이는 다음과 같은 반례에서 통과하지 못한다.

1
5
I 2
I 3
D -1
I 1
D 1

논리대로라면 '1 1'이 나와야 하지만 '2 1'이 나오고 만다.

이를 시뮬레이션해보면 두 queue에서 어떤 값은 pop이 되는데 다른 queue에서는 pop이 되지 않는 것을 볼 수 있었다. 즉, 서로 큐 간의 싱크가 안 맞는다.

이를 해결하기 위해 다른 블로그를 참고했다.

(+ 참고 https://velog.io/@mttw2820/%EB%B0%B1%EC%A4%80-7662.-%EC%9D%B4%EC%A4%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90)

 

블로그를 통해 나온 코드는 이렇다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int main() {
	int T;
	cin >> T;
	for (int i = 1; i <= T; i++) {
		// priority queue는 heap으로 구성되어있기 때문에 maxHeap(내림차순), minHeap(오름차순)으로 이름을 붙여줬다
		priority_queue<pair<int, int>> maxHeap;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
		bool visited[1000001] = { 0, }; // 각 인덱스별 방문 여부
		int k;
		cin >> k;
		for (int j = 1; j <= k; j++) {
			char idx;
			int num;
			cin >> idx >> num;
			if (idx == 'I') {
				maxHeap.push(make_pair(num, j));
				minHeap.push(make_pair(num, j));
				visited[j] = 1;
			}
			else if (idx == 'D') {
				if (num == 1) {
					// 싱크 맞추기
					while (!maxHeap.empty() && !visited[maxHeap.top().second]) {
						maxHeap.pop();
					}
					// 삭제
					if (!maxHeap.empty()) {
						visited[maxHeap.top().second] = false;
						maxHeap.pop();
					}
				}
				else if (num == -1) {
					// 싱크 맞추기
					while (!minHeap.empty() && !visited[minHeap.top().second]) {
						minHeap.pop();
					}
					// 삭제
					if (!minHeap.empty()) {
						visited[minHeap.top().second] = false;
						minHeap.pop();
					}
				}
			}
		}
		// 마지막으로 싱크 맞추기
		while (!maxHeap.empty() && !visited[maxHeap.top().second]) {
			maxHeap.pop();
		}
		while (!minHeap.empty() && !visited[minHeap.top().second]) {
			minHeap.pop();
		}

		if (maxHeap.empty() && minHeap.empty()) {
			cout << "EMPTY" << '\n';
		}
		else {
			cout << maxHeap.top().first << ' ' << minHeap.top().first << '\n';
		}
	}
	return 0;
}

visited 배열을 통해 방문 여부를 체크하면서 삭제할 때 다시 visited에 0으로 체크해주면서 싱크를 맞춰나가는 것이 이번 문제의 포인트다.

아까 통과하지 못했던 반례를 가져와보자.

1
5
I 2
I 3
D -1
I 1
D 1

'D 1'까지 즉, 마지막 명령까지는 틀렸던 코드와 똑같다.

현재 maxHeap에는 '2 1'이 있으며 minHeap에는 '1 3'이 있다. 하지만, 마지막에 싱크를 맞춰주면서 maxHeap의 2는 pop이 된다.

즉 '1 1'이 도출되며 정답이 된다.

(minHeap에 '1 3'이 남아있는데 3이 문제가 되는 것이 아니냐 라고 생각할 수 있지만 결론적으로 도출을 해내는 데에 있어서 3을 만날 경우에는 다시금 싱크를 맞추는 작업을 하기 때문에 문제가 되지는 않는다.)

---

이번 문제의 포인트

이번 문제의 포인트는 우선순위 큐를 두 개 선언해야 했다는 점

더 큰 포인트는 두 개의 큐지만 하나의 큐처럼 작동을 해야 하기 때문에 싱크를 맞춰주는 작업이 중요했다.

이를 visited 배열로 방문 여부를 파악했다는 점을 공부해두어야 할 거 같다.