[BOJ] C++ 7662 이중 우선순위 큐

2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

answer : 
EMPTY
333 -45

---

이중 우선순위 큐는 우선순위를 최대와 최소로 두 개 가지고 처리하는 우선순위 큐이다. 우선순위 큐를 두 개 선언하는 방법과 맵을 쓰는 방법 멀티 셋을 쓰는 방법을 떠올렸다. 맵을 떠올린 이유는 입력하는 원소가 중복이 될 수 있어서 키를 원소로 하고 value를 해당 원소의 개수로 하려고 했는데 굳이 짜보진 않았다. 우선순위 큐와 멀티 셋 중 고민하다가 우선순위 큐 두 개를 쓰는 것보다 멀티 셋 하나로 처리하는 게 공간적으로 이득을 보는 것 같아서 멀티 셋으로 짰다.

 

set 컨테이너 사용법과 포인터와 주소로 접근하기를 연습할 수 있었다. 마침 set 사용법이 조금 헷갈렸는데 잘 연습했다.

/** 우선순위 큐 7662 이중 우선순위 큐  **/
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        multiset<int, greater<int>> se;
        int n;
        cin >> n;

        for (int i = 0; i < n; i++)
        {
            string s;
            int x;
            cin >> s >> x;

            // 삽입인 경우
            if (s == "I")
            {
                se.insert(x);
            }
            // 삭제인 경우
            else
            {
                if (!se.empty())
                {
                    if (x == 1)
                        // 최댓값 삭제
                        se.erase(se.begin());
                    else
                        // 최솟값 삭제
                        se.erase(--se.end());
                }
            }
        }
        if (se.empty())
            cout << "EMPTY\n";
        else
        {
            cout << *se.begin() << " " << *--se.end() << "\n";
        }
    }
}