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

https://www.acmicpc.net/problem/7662

 

#include <iostream>
#include <queue>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        int k;
        cin >> k;
        int cnt = 0;
        priority_queue<int> maxq;
        priority_queue<int> minq;

        while (k--) {
            char op;
            int x;
            cin >> op >> x;
            if (op == 'I') {
                maxq.push(x);
                minq.push(-x);
                cnt++;
            } else if (op == 'D' && x == 1) {
                if (cnt > 0) {
                    maxq.pop();
                    cnt--;
                }
            } else if (op == 'D' && x == -1) {
                if (cnt > 0) {
                    minq.pop();
                    cnt--;
                }
            }
        }

        if (cnt == 0) cout << "EMPTY\n";
        else cout << maxq.top() << ' ' << -minq.top() << '\n';
    }

}

최댓값을 빼내기 위한 maxq와 최솟값을 빼내기 위한 minq, 이렇게 두개의 우선순위 큐를 사용해서 풀었다. 대신 minq에는 원래 값의 부호를 뒤집어서 넣어준다. (당연히 뺄 때도 다시 반전시켜야 함.) 처음에 이렇게 제출했는데 이십 몇퍼에서 틀렸다. (WA) 오늘도 어김없이 질문 게시판을 뒤져서 왜 틀렸는지 알아냈다.

최댓값을 뺄 때는 maxq.pop()을 쓰고 최솟값을 뺄 때는 minq.pop()을 썼는데, 최댓값을 뺄 때 maxq에서는 빠지지만 minq에서는 안 빠지고 마찬가지로 최솟값을 뺄 때 minq에서는 빠지지만 maxq에서는 안 빠진다는 문제점이 있다. 그래서 반례는 다음과 같다.

 

input
1
9
I 36
I 37
I 38
D 1
D 1
I 39
I 40
D -1
D -1

output
40 38

answer
40 40

 

#include <iostream>
#include <queue>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        int k;
        cin >> k;
        int cnt = 0;
        priority_queue<int> maxq;
        priority_queue<int> maxdq;
        priority_queue<int> minq;
        priority_queue<int> mindq;

        while (k--) {
            char op;
            int x;
            cin >> op >> x;
            if (op == 'I') {
                maxq.push(x);
                minq.push(-x);
                cnt++;
            } else if (op == 'D' && x == 1) {
                if (cnt > 0) {
                    while (!maxdq.empty() && maxdq.top() == maxq.top()) {
                        maxdq.pop();
                        maxq.pop();
                    }
                    mindq.push(-maxq.top());
                    maxq.pop();
                    cnt--;
                }
            } else if (op == 'D' && x == -1) {
                if (cnt > 0) {
                    while (!mindq.empty() && mindq.top() == minq.top()) {
                        mindq.pop();
                        minq.pop();
                    }
                    maxdq.push(-minq.top());
                    minq.pop();
                    cnt--;
                }
            }
        }

        while (!maxdq.empty() && maxdq.top() == maxq.top()) {
            maxdq.pop();
            maxq.pop();
        }
        while (!mindq.empty() && mindq.top() == minq.top()) {
            mindq.pop();
            minq.pop();
        }

        if (cnt == 0) cout << "EMPTY\n";
        else cout << maxq.top() << ' ' << -minq.top() << '\n';
    }
}

그래서 새로운 우선순위 큐 2개를 더 만들었다... ㅎㅎ maxdq는 maxq에서는 빠졌지만 minq에서는 빠지지 않은 수를 저장하는 우선순위 큐이고, mindq는 minq에서는 빠졌지만 maxq에서는 빠지지 않은 수를 저장하는 우선순위 큐이다. 그런데도 틀렸다... (WA)

 

#include <iostream>
#include <queue>
using namespace std;

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

    int t;
    cin >> t;

    while (t--) {
        int k;
        cin >> k;
        int cnt = 0;
        priority_queue<long long> maxq;
        priority_queue<long long> maxdq;
        priority_queue<long long> minq;
        priority_queue<long long> mindq;

        while (k--) {
            char op;
            long long x;
            cin >> op >> x;
            if (op == 'I') {
                maxq.push(x);
                minq.push(-x);
                cnt++;
            } else if (op == 'D' && x == 1) {
                if (cnt > 0) {
                    while (!maxdq.empty() && maxdq.top() == maxq.top()) {
                        maxdq.pop();
                        maxq.pop();
                    }
                    mindq.push(-maxq.top());
                    maxq.pop();
                    cnt--;
                }
            } else if (op == 'D' && x == -1) {
                if (cnt > 0) {
                    while (!mindq.empty() && mindq.top() == minq.top()) {
                        mindq.pop();
                        minq.pop();
                    }
                    maxdq.push(-minq.top());
                    minq.pop();
                    cnt--;
                }
            }
        }

        while (!maxdq.empty() && maxdq.top() == maxq.top()) {
            maxdq.pop();
            maxq.pop();
        }
        while (!mindq.empty() && mindq.top() == minq.top()) {
            mindq.pop();
            minq.pop();
        }

        if (cnt == 0) cout << "EMPTY\n";
        else cout << maxq.top() << ' ' << -minq.top() << '\n';
    }
}

이번에는 자료형 문제였다. 입력으로 들어오는 x의 범위는 -2^31~2^31-1인데 minq 등에 넣을 때는 부호를 바꿔서 넣으니 오버플로우 문제가 발생하는 것이었다. 그래서 x와 모든 우선순위 큐들의 원소를 다 int에서 long long으로 바꿔주었다. 그랬더니 정답! (AC)