백준 7662번 이중 우선순위 큐 - C++(cpp) 풀이

---

 

문제 제목에서부터 알 수 있듯이 우선순위 큐를 써야 하는데, 스위프트에는 라이브러리로 우선순위 큐를 제공하지 않아서 C++로 풀었다.

1. 최댓값은 최댓값 큐에서 찾는다.
2. 최솟값은 최솟값 큐에서 찾는다.
3. 반대쪽 큐에서 제거된 값인지 구별하기 위해, map에 해당 숫자가 현재 몇 개 남아있는지 기록한다.

---

 먼저 최대값과 최솟값을 모두 알아내야 하므로 우선순위 큐를 2개 운영해야 한다. 하나는 최댓값용, 하나는 최솟값용으로. 근데 이렇게 되면 삭제를 할 때 문제가 된다.

 최솟값을 삭제하라는 쿼리가 들어오면, 최솟값 큐에서 pop을 할 것이다. 근데 이 최솟값이 최댓값 큐에는 남아있게 된다.

 따라서 반대 큐에서 삭제 여부를 알 수 있도록, 어떤 수 x가 현재 몇 개 남아 있는지를 기록해두어야 한다. 수 범위가 커서 배열로는 불가능하다. map에다 기록해주면 된다.

 이제 최댓값 큐든, 최솟값 큐든, 큐에서 어떤 수 x를 pop 할 때, x의 남아있는 개수를 확인해서 그것이 유효한 숫자인지를 체크해주면 된다. 만약에 map[x] = 0이면 반대쪽 큐에서 삭제한 무효한 수이므로 스킵해준다.

---

 테스트 케이스가 여러 개니까 매 테스트 케이스마다 우선순위 큐랑 map을 비워주는 것을 잊지 말자. 이것 때문에 틀렸었다ㅠㅠ 사악하게 예제 입출력은 이전 테스트 케이스가 EMPTY..

반응형

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

priority_queue<int, vector<int>, greater<int>> min_pq;  // 최소힙
priority_queue<int, vector<int>, less<int>> max_pq;     // 최대힙
map<int, int> cnt; // cnt[i]: 남아있는 i의 개수

void insert(int n) {
    min_pq.push(n);
    max_pq.push(n);
    cnt[n]++;
}

void deleteMin() {
    if (!min_pq.empty()) {
        cnt[min_pq.top()]--;
        min_pq.pop();
    }
}

void deleteMax() {
    if (!max_pq.empty()) {
        cnt[max_pq.top()]--;
        max_pq.pop();
    }
}

// 반대큐에서 삭제된 값이 top에 남아있지 않도록 정리
void cleanPqs() {
    while (!min_pq.empty() && cnt[min_pq.top()] == 0) {
        min_pq.pop();
    }
    
    while (!max_pq.empty() && cnt[max_pq.top()] == 0) {
        max_pq.pop();
    }
}

int main()
{
    int T, n, k;
    char cmd;
    
    cin >> T;
    while (T--) {
        while (!min_pq.empty()) { min_pq.pop(); }
        while (!max_pq.empty()) { max_pq.pop(); }
        cnt.clear();
        
        cin >> k;
        for (int i = 0; i < k; i++) {
            cin >> cmd >> n;
            
            if (cmd == 'I') insert(n);
            else {
                if (n == 1) deleteMax();
                else deleteMin();
                cleanPqs();
            }
        }
        
        cleanPqs();
        if (max_pq.empty() || min_pq.empty()) cout << "EMPTY\n";
        else cout << max_pq.top() << " " << min_pq.top() << "\n";
    }

    return 0;
}