[BOJ 7662] 이중 우선순위 큐

7662번: 이중 우선순위 큐

1. 문제 설명

 

2. 예제 설명

 

3. 구현 아이디어 1 - 틀렸습니다.

C++의 priority_queue에서는 가장 위(top)의 원소만 반환할 수 있다.

 

매 연산마다 우선순위 큐를 뒤집는 것은 비효율적이기 때문에 최댓값과 최솟값 둘 다 접근하기 위해서는 우선순위 큐를 2개 만들어야 한다.

 

그리고 중요한 것이 2개의 우선순위 큐를 동기화해주는 것이다.

최댓값 또는 최솟값을 삭제할 때 하나의 큐에서만 삭제하면 다음 연산을 진행할 때 연산이 원하는대로 이루어지지 않기 때문이다.

 

우선순위 큐를 동기화해주기 위해 map 타입의 변수 mp를 만들어 해당 원소가 현재 이중 우선순위 큐에 몇 개 있는지 저장해주었다.

삭제 연산을 할 때마다 mp[i]--를 해주었고, mp[i]가 0이라면 2개의 큐 중 하나에 있더라도 결과적으로는 이중 우선순위 큐에 존재하지 않는 것이기 때문에 우선순위 큐에서 pop을 해주었다.

 

💡 핵심 포인트 정리
1. 우선순위 큐를 2개 사용하자
2. 원소가 몇 개 있는지 map 등을 사용하여 저장하고, 0개일 경우 반대 큐에서도 pop해주자

 

#include <bits/stdc++.h>

using namespace std;

int t; // 테스트 케이스
int q; // 적용할 연산의 개수
char a; // 연산 - D 또는 I
int b; // 정수

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

    cin >> t;
    while (t--) {
        priority_queue<int> pq1; // 큰 값 우선
        priority_queue<int> pq2; // 작은 값 우선
        map<int, int> mp;

        cin >> q;
        while (q--) {
            cin >> a >> b;
            if (a == 'I') { // 삽입
                pq1.push(b);
                pq2.push(-b);
                mp[b] ++;
            } else if (a == 'D') { // 삭제
                if (b == 1) { // 최댓값을 삭제
                    if (pq1.empty()) continue;
                    mp[pq1.top()] --;
                    pq1.pop();
                } else if (b == -1) { // 최솟값을 삭제
                    if (pq2.empty()) continue;
                    mp[-pq2.top()] --;
                    pq2.pop();
                }

                // 반대 큐에서 삭제된 값이 top에 남아있지 않도록 정리
                while (!pq1.empty() && mp[pq1.top()] == 0) pq1.pop();
                while (!pq2.empty() && mp[-pq2.top()] == 0) pq2.pop();
            }
        }

        // 결과 출력
        if (pq1.empty() || pq2.empty()) {
            cout << "EMPTY\n";
            continue;
        }
        cout << pq1.top() << " " << -pq2.top() << "\n";
    }

    return 0;
}

 

4. 구현 아이디어 2 - 맞았습니다!!

구현 아이디어 1처럼 구현했을 때 계속 93%쯤에서 틀렸습니다가 나왔다 :(

질문 게시판을 통해 입력으로 INT_MAX나 INT_MIN이 들어올 경우 스택오버플로우가 발생하는 것이 원인인 것을 알 수 있었다.

 

INT_MAX는 2147483647이고, INT_MIN은 -214783648이기 때문에 INT_MIN의 부호를 바꾸면 스택오버플로우가 발생하는 것이다.

 

다른 사람의 풀이를 참고하여 less, greater을 명시해주어 앞에 -를 붙이지 않고 최대 힙과 최소 힙을 구현할 수 있음을 알게 되었다.

아래와 같이 변수 선언을 바꾸고, pq2.top() 앞에 붙은 -를 지워서 문제를 해결할 수 있었다.

// Before
priority_queue<int> pq1; // 최댓값 우선
priority_queue<int> pq2; // 최솟값 우선

// After
priority_queue<int, vector<int>, less<int>> pq1;
priority_queue<int, vector<int>, greater<int>> pq2;