백준 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;
}