7662번-이중 우선순위 큐

중요 지식

---

multiset - 중복된 값을 포함하며, 자동적으로 정렬이 돼서 문제에 적합하다

코드

---

#include <iostream>
#include <set>

using namespace std;

int main(){
    int T, N;
    multiset<long long> multiSet;

    cin >> T;
    for(int i = 0; i < T; i++){
        multiSet.clear();

        cin >> N;

        for(int j = 0; j < N; j++){
            char x;
            long long y;

            cin.ignore(10, '\n');
            scanf("%c %lld", &x, &y);

            if(x == 'I'){
                multiSet.insert(y);
            }
            else if(!multiSet.empty()){
                if(y == 1) 
                    multiSet.erase(--multiSet.end());
                else 
                    multiSet.erase(multiSet.begin());
            }
        }

        if(!multiSet.empty()){
            long long max = *--multiSet.end();
            long long min = *multiSet.begin();

            printf("%lld %lld\n", max, min);
        }
        else 
            printf("EMPTY\n");
    }
    return 0;
}

풀이

---

자료구조 set을 사용하면 쉽게 풀 수 있다