[백준/C++] 7662번: 이중 우선순위 큐

문제

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

---

문제 요약

이중 우선순위 큐란 전형적인 우선순위 큐처럼 데이터를 삽입/삭제할 수 있는 자료구조이다.

 

이 때, 일반적인 우선순위 큐와 달리 최솟값과 최댓값 중 선택해서 삭제할 수 있다.

 

연산 후, 이중 우선순위 큐 내 최댓값과 최솟값을 출력한다.

---

코드

#include <iostream>
#include <string>
#include <set>

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;

        multiset<int> ms;

        while (k--) {
            string command;
            int num;

            cin >> command >> num;

            if (command == "I") {
                ms.insert(num);
            }

            else {
                if (ms.empty()) {
                    continue;
                }

                if (num == 1) {
                    ms.erase(prev(ms.end()));
                }
                else {
                    ms.erase(ms.begin());
                }
            }
        }

        if (ms.empty()) {
            cout << "EMPTY" << "\n";
        }
        else {
            cout << *prev(ms.end()) << " " << *ms.begin() << "\n";
        }

    }
    
    return 0;
}

---

코드 설명

균형 이진 트리를 기반으로 구현된 Multiset으로 문제를 해결한다.

 

원소 삽입 시, 정렬 순서를 위해 O(log n)의 시간 복잡도를 갖는다.

 

최소 값에 접근 시, begin() 반복자를, 최소 값에 end() 반복자를 이용한다.

---

고찰

end() 반복자는 마지막 원소 다음 주소를 가리키므로, prev를 이용한다.