백준 7662 이중 우선순위 큐 (C++)

7662번: 이중 우선순위 큐

우선순위 큐를 이용한 문제이다. 우선순위 큐를 양방향으로 구현해주기 위해 오름차순과 내림차순 두가지 우선순위 큐를 사용해주었다.
반복문을 돌며 커맨드에 따라 동작을 하게 되는데 중요한 점은 cnt를 통해 n의 개수를 카운트해주는 점이다. 이 카운트를 통해 반대 큐에서 pop이 일어날 경우 카운트가 0일 경우 pop을 해주게 된다. 이를 통해 최댓값과 최솟값을 구하고 출력해주었다.
굉장히 오래 걸린 문제였다. 문제 자체의 로직은 어렵지 않은데 자잘한 실수가 진짜 엄청나게 많았다... 첫번째로 백터를 통해 커맨드를 입력받는데 이를 테스트 케이스를 돌 때 초기화해주지 않아 12%에서 계속 오류가 났다... 이후로 93%에서 계속 해서 오류가 나서 긴 시간동안 이유를 찾아 해맸었다.... 이것이 두번째 실수인데 이유인 즉슨 내림차순 백터를 나는 일반 오름차순 백터에 부호를 마이너스로 바꾸어 저장해 내림차순으로 구현을 했었는데 문제를 보면 범위가 -2^31 이상 (!!!!!) 2^31 미만이다. -2^31의 부호를 바꾸어주니 범위를 벗어나 오류가 계속 났었던 것이었다.... 그리고 찾아보니 multiset이 이중 우선순위 큐와 유사하게 동작한다는 점도 알게되었다. 많은 것들을 배울 수 있었던 문제였다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int k;
vector<pair<char, int>> command;
map<int, int> cnt;

void solution() {
    priority_queue<int, vector<int>, less<int>> up;
    priority_queue<int, vector<int>, greater<int>> lo;

    for (int i = 0; i < command.size(); i++) {
        char c = command[i].first;
        int n = command[i].second;

        if (c == 'I') {
            up.push(n);
            lo.push(n);
            cnt[n]++;
        }
        else {
            if (n == 1) {
                if (!up.empty()) {
                    cnt[up.top()]--;
                    up.pop();
                }
            }
            else {
                if (!lo.empty()) {
                    cnt[lo.top()]--;
                    lo.pop();
                }
            }
            while (!up.empty() && cnt[up.top()] == 0) up.pop();
            while (!lo.empty() && cnt[lo.top()] == 0) lo.pop();
        }
    }

    while (!up.empty() && cnt[up.top()] == 0) up.pop();
    while (!lo.empty() && cnt[lo.top()] == 0) lo.pop();

    if (up.empty() || lo.empty()) cout << "EMPTY" << "\n";
    else cout << up.top() << " " << lo.top() << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        command.clear();
        cnt.clear();

        cin >> k;

        char c;
        int n;
        for (int i = 0; i < k; i++) {
            cin >> c >> n;

            command.push_back({ c,n });
        }

        solution();
    }

    return 0;
}