백준[7662] 이중 우선순위 큐

문제 설명

문제 링크

http://icpc.me/7662

7662번: 이중 우선순위 큐

풀이

multiset을 이용하여 풀 수 있다. 

multiset은 정렬이 되어있는 균형 이진트리 형태로 구현돼있기 때문에 가장 큰 값과 가장 작은 값을 쉽게 구할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        multiset<int> ms;
        int n; scanf("%d", &n);
        while (n--) { 
            char cmd; int num; scanf(" %c %d", &cmd, &num);
            if (cmd == 'I') {
                ms.insert(num);
            } else {
                if (ms.empty()) continue;
                if (num == -1) {
                    int k = *ms.begin();
                    ms.erase(ms.lower_bound(k));
                } else {
                    int k = *ms.rbegin();
                    ms.erase(ms.lower_bound(k));
                }
            }
        }
        if (ms.empty()) printf("EMPTY\n");
        else printf("%d %d\n", *ms.rbegin(), *ms.begin());
    }    
}