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

일반적으로 최대 힙(MAX HEAP), 최소 힙(MIN HEAP)을 통해 구현할 수 있겠지만

사실 이걸 자료구조 시간때 직접 구현하는 방법만 알았지 STL을 어떻게 써야 할 지 몰랐다.

당연히 다른 블로그들을 보게 되면 대부분 최대/최소 힙을 사용하여서 문제를 풀었었다.

그런데 어느 한 블로그를 보고 이걸 multiset으로 푸신분이 계셔 그분의 코드를 참고했다.

 

multiset은 c++의 STL이며 set container와 달리 key가 중복 가능한 set을 구현할 수 있다. 

• 트리 자료구조이다.
• multiset에 원소를 넣으면 자동으로 오름차순 정렬이 된다.
• 중위 순회로 원소에 접근한다. (중위 순회는 트리에서 루트 노드를 중간순서에 방문하는 순회)

자세한 개념은 아래의 블로그를 참고하자

https://blockdmask.tistory.com/80

 

#include <iostream>
#include <set>

using namespace std;

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

    int t;
    cin >> t;

    int n;
    while (t--) {
        cin >> n;
        char order;
        int num;
        multiset<int> ms;
        while (n--) {
            cin >> order >> num;
            if (order == 'I')
                ms.insert(num);
            else {
                if (!ms.empty() && num == -1)
                    ms.erase(ms.begin());
                else if (!ms.empty() && num == 1) {
                    auto iter = ms.end();
                    iter--;
                    ms.erase(iter);
                }
            }
        }
        if (ms.empty())
            cout << "EMPTY" << '\n';
        else {
            auto end_iter = ms.end();
            end_iter--;
            cout << *end_iter << ' ' << *ms.begin() << '\n';
        }
    }
    return 0;
}