[BOJ 7662 // C++] 이중 우선순위 큐

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7662번 문제인 이중 우선순위 큐이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

우선순위 큐(priority queue)는 자료의 추가가 수시로 이루어지는 경우, 우선순위가 가장 높은(또는 낮은) 자료를 항상 빠르게 꺼낼 수 있는 자료구조이다.

 

이 문제에서는 쿼리를 통해 자료를 빈번히 추가하고 우선순위가 가장 높은 자료 또는 가장 낮은 자료를 쿼리가 들어온 시점을 기준으로 제거한다.

이런 작업을 수행할 수 있는 우선순위 큐를 double-ended priority queue라고 한다.

 

double-ended priority queue를 구현하는 대표적인 방법 중 하나는 min-max heap을 이용하는 것이다.

그러나 이 문제는 자료구조를 처음서부터 코딩하라는 문제가 아니기에 글쓴이는 min-max heap을 직접 구현하지는 않았다.

min-max heap에 관심이 있다면 다음 위키백과 링크를 참고하자.

en.wikipedia.org/wiki/Min-max_heap

 

글쓴이는 stl에 들어있는 std::priority_queue를 활용하여 문제를 풀었다.

 

std::priority_queue는 max heap 자료구조인데, 정수 자료의 경우 자료를 넣을 때 -1을 곱해 넣고 꺼낼 때 다시 -1을 곱하는 방식으로 min heap으로도 사용할 수 있다.

(단, 일반적인(signed) int형의 경우 양수와 음수가 완전히 대응되지 않으므로 이에 주의한다.)

 

문제를 푼 방식은 단순하다.

 

1) 새로운 정수가 들어온다면 이 정수를 max heap과 min heap에 각각 넣는다.

 

2-1) 최댓값을 지우라는 명령이 들어오면 max heap에서 최댓값을 지우고, min heap에서 다음에 이 수가 나오면 지워야 한다고 기록해둔다. 이 수들은 min heap에서 숫자가 지워지는 순서대로 만나게 될 것이므로, 또 다른 min heap에 저장해두면 지워야 할 때 쉽게 확인하고 지울 수 있다.

 

2-2) 최솟값을 지우라는 명령이 들어오면 min heap서 최솟값을 지우고, max heap에서 다음에 이 수가 나오면 지워야 한다고 기록해둔다. 이 수들은 max heap에서 숫자가 지워지는 순서대로 만나게 될 것이므로, 또 다른 max heap에 저장해두면 지워야할 때 쉽게 확인하고 지울 수 있다.

 

3) max heap과 min heap에서 지워야 할 수를 모두 지운다.

 

4) 1~3을 반복한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using std::priority_queue;
using std::cin;
using std::cout;

void solve() {
    priority_queue<long long> mxpq;
    priority_queue<long long> mxpqchk;
    priority_queue<long long> mnpq;
    priority_queue<long long> mnpqchk;
    
    int k;
    cin >> k;
    
    char type;
    long long n;
    for (int i = 0;i < k;i++) {
        cin >> type >> n;
        if (type == 'I') {
            mxpq.push(n);
            mnpq.push(-1*n);
        }
        else {
            if (n == 1 and mxpq.size()!=0) {
                long long x = mxpq.top();
                mnpqchk.push(-1*x);
                mxpq.pop();
            }
            else if (n == -1 and mnpq.size()!=0) {
                long long x = -1*mnpq.top();
                mxpqchk.push(x);
                mnpq.pop();
            }
            int sz1 = mxpq.size();
            int sz2 = mxpqchk.size();
            while (sz1 != 0 and sz2 != 0) {
                if (mxpq.top() == mxpqchk.top()) {
                    mxpq.pop();
                    mxpqchk.pop();
                    sz1 = mxpq.size();
                    sz2 = mxpqchk.size();
                }
                else break;
            }
            sz1 = mnpq.size();
            sz2 = mnpqchk.size();
            while (sz1 != 0 and sz2 != 0) {
                if (mnpq.top() == mnpqchk.top()) {
                    mnpq.pop();
                    mnpqchk.pop();
                    sz1 = mnpq.size();
                    sz2 = mnpqchk.size();
                }
                else break;
            }
        }
    }
    if (mxpq.size()==0) cout << "EMPTY\n";
    else cout << mxpq.top() << ' ' << -1*mnpq.top() << "\n";
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    for (int i = 0;i < T;i++) {
        solve();
    }

    return 0;
}