백준 7662 이중 우선순위 큐 / C++

문제 : 7662

풀이 point

우선순위 큐를 통해 풀수도 있지만 트리를 이용하고 중복을 허용하는 multiset을 활용하여 문제를 풀 수 있다.

풀이 방법

multiset은 중복을 허용하므로 값을 집어넣고 가장 최소와 가장 최대를 뽑을 수 있다.
트리 구조이므로 모든 연산은 O(logn)이다.

최대값은 std::prev(set.end()) (end는 맨끝 값 + 1 좌표를 가르키기 때문)
최소값은 set.begin()이다.

begin, end모두 iterator자료형이므로 값을 출력하고 싶으면 역참조 하면 된다.

코드

//백준 7662, 이중 우선순위 큐

#include <iostream>
#include <set>

int main (){

    int T, N;
    std::cin >> T;
    while(T--){
        std::multiset<int> set;
        std::cin >> N;
        char a; int b;
        for(int i{0}; i<N; ++i){
            std::cin >> a >> b;
            if(a == 'I'){
                set.insert(b);
            }
            else{
                if(set.empty()) continue;
                else if(b == -1) set.erase(set.begin());
                else set.erase(std::prev(set.end()));
            }
        }
        if(set.empty()) std::cout << "EMPTY" << '\n';
        else std::cout << *std::prev(set.end()) << ' ' << *set.begin() << '\n';
    }

    return 0;
}