문제
이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.
정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라. baekjoon
코드
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
int main() {
int tc;
cin >> tc;
while (tc--) {
int k;
cin >> k;
vector<bool> is_in(1000000);
// first: value, second: cmd index
priority_queue<pair<int, int>> pq_down;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq_up;
for (int i = 0; i < k; i++) {
char cmd;
int cmd_int;
cin >> cmd >> cmd_int;
if (cmd == 'I') {
pq_down.push(make_pair(cmd_int, i));
pq_up.push(make_pair(cmd_int, i));
is_in[i] = true;
} else {
// D
if (cmd_int == 1) {
while (!pq_down.empty() && !is_in[pq_down.top().second]) pq_down.pop();
if (!pq_down.empty()) {
is_in[pq_down.top().second] = false;
pq_down.pop();
}
} else {
while (!pq_up.empty() && !is_in[pq_up.top().second]) pq_up.pop();
if (!pq_up.empty()) {
is_in[pq_up.top().second] = false;
pq_up.pop();
}
}
}
}
while (!pq_down.empty() && !is_in[pq_down.top().second]) pq_down.pop();
while (!pq_up.empty() && !is_in[pq_up.top().second]) pq_up.pop();
string result;
if (pq_down.empty() && pq_up.empty()) result = "EMPTY";
else result = to_string(pq_down.top().first) + " " + to_string(pq_up.top().first);
cout << result << endl;
}
}
풀이
우선순위 큐를 2개 준비한다. 하나는 큰 수가 우선순위가 높은, 즉 오름차순으로 정렬되는 큐와 다른 하나는 내림차순으로 정렬(이게 기본값)되는 큐다. I
명령에는 두 큐에 모두 삽입한다. D
명령시 하나의 큐에서만 삭제하게 되지만, 다른 큐에서도 이 값은 삭제되어야 한다. 하지만 즉각적으로 삭제하기엔 해당 값을 찾아서 삭제해야 하는데 비효율적이기도 하고, 기본적으로 제공되는 메소드가 없어서 불편하다. 결국 해당 값이 유효하지 않다는 표시(is_in
)만 하고, 각 큐의 값에 접근할 일이 있을 때마다 이게 유효한지 안 유효한지 표식을 확인하면 된다.
원래 삽입되는 값을 통해 표시하는게 더 직관적으로 생각났었다. 같은 숫자가 여러번 나올 수 있으므로 vector<int> is_in(INT_MAX)
이런식으로 하려고 했었다. 하지만 스택이 너무 작아서 21억 크기만큼 메모리를 미리 잡아먹는게 안되나보다. new
로 동적 할당해서 힙에 생성해야 하는데 벡터의 주소가 넘어오기 때문에 이용하기가 매우 불편하다. 애초에 저만한 크기가 필요하다는 것 자체가 잘못 푼게 아닌가 싶다. 그래서 여기서는 값의 유효성을 명령어의 순서로 판단한다. 순서는 중복이 생길 수 없으니 bool
로 표기해도 문제가 없다.