문제 출처

1. 문제설명

  • 우선순위 큐에 입력되는 원소 자체가 우선순위가 된다.
    • 입력되는 원소는 중복될 수 있다.
  • 큐에 연산이 주어졌을 때 최종적으로 저장된 최댓값과 최소값을 출력하라



2. 알고리즘 설계

  • STL을 사용할 수 있는가?의 문제이다.
  • N이 매우 크기 때문에 $lgN$ 알고리즘을 사용해야 한다.
  • 우선순위 큐를 사용해도 되지만,
  • 이진탐색트리인 set을 사용하였다.
    • 원소가 중복을 허용하므로, multiset을 사용한다.
  • multiset을 사용할 때, erase(num)을 하면 같은 값을 전부 지워버린다.
    • 이 문제에서는 최솟값, 최댓값이므로, iterator만 잘 사용하면 된다.
    • 만약 특정원소라면, erase 인자로 lower_bound 또는 upper_bound를 넣어야 한다.



3. 전체 코드

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

int main(){
    int TC, t, k;
    cin >> TC;
    while(TC--) {
        multiset<int> ms;

        cin >> t;
        while(t--) {
            char op;
            int n;
            cin >> op >> n;

            if(op == 'I') ms.insert(n);
            else {
                if(ms.empty()) continue;
                if(n == 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;
}