백준 7662 이중 우선 순위 큐

 

출처 : www.acmicpc.net/problem/7662

 

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다.

전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다.

 

이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 

 

주어진 정수 값 자체를 우선순위라고 했을 때, 주어진 명령이 모두 수행된 후 최솟값과 최댓값, 또는 비어있을 경우 "EMPTY"를 출력하는 문제

 

풀이

우선 문제를 읽으면서 생각나는건, 최대 힙과 최소 힙을 둘 다 만들어 두어야 한다는 점이다.

문제에선 "이중 우선 순위 큐"라고 하지만, 사실 우선순위가 가장 높은 데이터와 가장 낮은 데이터 둘 다 O(1) 만에 삭제하는 자료구조를 직접 구현할 방법은 없다. (아마도?)

따라서 우리는 최대 힙, 최소 힙을 둘 다 만들어 두고 이를 적용시켜야 하는데, 다만 문제 되는 부분은

만약 우선순위가 가장 높은 데이터를 삭제했을 경우 (최대 힙에서 pop을 한 경우)

최소 힙에는 아직 이 데이터가 남아 있다는 점이다.

 

이 부분은 "어떤 연산을 하더라도 두 힙의 원소의 개수, 종류가 다를 수 없다는 점"에서 착안해

따로 전체 배열에서 특정 원소가 몇 개 있는지를 기록해두고, 삽입, 삭제가 나왔을 때 +1, -1 처리해준 다음

나중에 삭제 시, 배열에 지금 없을 경우(다른 힙에서 삭제된 경우) 그냥 pop 하고, 다음 원소를 삭제하면 된다.

그리고 마지막에 원소를 출력 할 때도, 이 과정을 한 번 거쳐야 정확히 힙에 있는 원소를 출력할 수 있게 된다.

 

유의할 점은 문제에서 입력되는 정수가 32비트이기 때문에 정수 배열이 아닌, map을 이용해 기록해둬야 메모리 초과를 막을 수 있다. 이 부분은 명령 개수가 작기 때문에 할 수 있는 방법이다.

 

위 과정은 아래 코드 한 줄로 요약되니 참고하자. (최대 힙의 경우)

while (!max_pq.empty() && mp[max_pq.top()] == 0) max_pq.pop();

 

소스 코드(.cpp)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) {
		priority_queue<int, vector<int> >max_pq; // 최대 힙
		priority_queue<int, vector<int>, greater<int> >min_pq; // 최소 힙
		map<int, int>mp;
		int k; cin >> k;
		for (int i = 0; i < k; i++) {
			char cmd; cin >> cmd;
			if (cmd == 'I') {
				int n; cin >> n;
				max_pq.push(n);
				min_pq.push(n);
				mp[n]++;
			}
			else {
				int n; cin >> n;
				if (n == 1) {
					while (!max_pq.empty() && mp[max_pq.top()] == 0) max_pq.pop();
					if (max_pq.empty()) continue;
					else {
						int x = max_pq.top();
						max_pq.pop();
						mp[x]--;
					}
				}
				else {
					while (!min_pq.empty() && mp[min_pq.top()] == 0) min_pq.pop();
					if (min_pq.empty()) continue;
					else {
						int x = min_pq.top();
						min_pq.pop();
						mp[x]--;
					}
				}
			}
			while (!max_pq.empty() && mp[max_pq.top()] == 0) max_pq.pop();
			while (!min_pq.empty() && mp[min_pq.top()] == 0) min_pq.pop();
			
		}
		if (max_pq.empty()) cout << "EMPTY\n";
		else {
			cout << max_pq.top() << " " << min_pq.top() << "\n";
		}
	}
	return 0;
}