[C++] 이중 우선순위 큐 (7662번)

이중 우선순위 큐

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적용할 연산의 개수를 나타내는 정수 k (k ≤ 1,000,000)가 주어진다. 이어지는 k 줄 각각엔 연산을 나타내는 문자(‘D’ 또는 ‘I’)와 정수 n이 주어진다. ‘I n’은 정수 n을 Q에 삽입하는 연산을 의미한다. 동일한 정수가 삽입될 수 있음을 참고하기 바란다. ‘D 1’는 Q에서 최댓값을 삭제하는 연산을 의미하며, ‘D -1’는 Q 에서 최솟값을 삭제하는 연산을 의미한다. 최댓값(최솟값)을 삭제하는 연산에서 최댓값(최솟값)이 둘 이상인 경우, 하나만 삭제됨을 유념하기 바란다.

만약 Q가 비어있는데 적용할 연산이 ‘D’라면 이 연산은 무시해도 좋다. Q에 저장될 모든 정수는 32-비트 정수이다. 

출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 Q에 남아 있는 값 중 최댓값과 최솟값을 출력하라. 두 값은 한 줄에 출력하되 하나의 공백으로 구분하라. 만약 Q가 비어있다면 ‘EMPTY’를 출력하라.

 

---

문제풀이

 

문제 제목이 이중 우선순위 큐라서 나도 모르게 큐를 두 개 사용하는 풀이법을 떠올렸다.

두 개의 우선순위 큐(민 힙, 맥스 힙)를 사용해서 풀어 보았다.

우선순위 큐는 기본적으로 내림차순 정렬이다.(맥스 힙)

오름차순 정렬로 만드는 방법은 여러 개가 존재하는데, 1. 저장할 때 값에 -를 붙인다. 2. vector<int>, greater<int>를 우선순위 큐 생성할 때 사용한다.

 

나는 1번 방법으로 했다.

 

1. 두 큐를 생성한다. 하나의 unordered_map(um)을 생성한다 -> 이건 삭제 여부 판단을 위함.

2. I일 경우 맥스 힙에는 그대로 값을 넣고, 민 힙에는 -를 붙여 넣어준다. 그리고 그 값을 um에 key로 넣어 1 증가시켜준다.

 

3. D일 경우 1, -1 해당하는 힙의 맨 앞 숫자를 pop 해주고, 그 값을 um에 key로 넣어 1 감소시켜준다.

민 힙과 맥스 힙 둘 다 반복문을 돌며 맨 앞의 값을 가져와 um에 key로 넣어 이게 0인지 아닌지 확인한다.

0이면 제거가 된 값이므로 pop 해준다.

 

요래 풀었는데... 큰 문제가 하나 있었다. 바로 정수 범위다. 양수 범위보다 음수 범위가 1 크기 때문에 -를 붙여줄 경우 문제가 발생한다... long long int로 바꾸어주거나 2번 방법으로 풀면 해결이 가능하다.

 

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

int n, k;
    
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> k;
        priority_queue<long long int> hq, lq;
        unordered_map<long long int, long long int> um;
        for(int j=0; j<k; j++) {
            char c;
            cin >> c;
            // 삽입 
            if(c == 'I') {
                long long int tmp;
                cin >> tmp;
                um[tmp]++;
                hq.push(tmp);
                lq.push(-tmp);
            }
            // 삭제 
            if(c == 'D') {
                int tmp;
                cin >> tmp;
                if(tmp == 1 && !hq.empty()) {
                    int rm = hq.top();
                    um[rm]--;
                    hq.pop();
                }
                else if(tmp == -1 && !lq.empty()) {
                    int rm = -lq.top();
                    um[rm]--;
                    lq.pop();
                }
                // 맨 앞 값이 이미 삭제된 값인지 확인 
                while(!lq.empty()) {
                    if(um[-lq.top()] == 0)
                        lq.pop();
                    else
                        break;
                }
                while(!hq.empty()) {
                    if(um[hq.top()] == 0)
                        hq.pop();
                    else
                        break;
                }
            }
        }
        if(hq.empty() && lq.empty()) {
            cout << "EMPTY" << "\n";
        }
        else {
            cout << hq.top() << " " << -lq.top() << "\n";
        }
    }
    return 0;
}

 

 

다른 사람들 풀이를 보니 multiset으로 풀 수도 있다. 이건 공간을 덜 잡아먹는다. 이건 생각도 못했다..