이중 우선순위 큐 7662

문제

접근 방법

우선순위를 최대, 최소로 하여 2개의 우선순위 큐를 만든다.
이후 최대, 최소에서 이미 사용한 값인지 확인해야 하는데 중복도 가능하므로 map을 사용해 주면 좋다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        priority_queue<int> hq;
        priority_queue<int, vector<int>, greater<int>> lq;
        unordered_map<int, int> um;
        int k;
        cin >> k;
        while (k--)
        {
            char com;
            int num;
            cin >> com >> num;
            if (com == 'I')
            {
                ++um[num];
                hq.push(num);
                lq.push(num);
            }
            else
            {
                if (num == 1)
                {
                    while (!hq.empty() && !um[hq.top()])
                        hq.pop();
                    if (hq.empty())
                        continue;
                    --um[hq.top()];
                    hq.pop();
                }
                else
                {
                    while (!lq.empty() && !um[lq.top()])
                        lq.pop();
                    if (lq.empty())
                        continue;
                    --um[lq.top()];
                    lq.pop();
                }
            }
        }
        while (!hq.empty() && !um[hq.top()])
            hq.pop();
        if (hq.empty())
        {
            cout << "EMPTY\n";
            continue;
        }
        while (!lq.empty() && !um[lq.top()])
            lq.pop();
        cout << hq.top() << " " << lq.top() << "\n";
    }

    return 0;
}

풀이

숫자의 범위가 큰 것은 map의 형태를 사용하는 것으로 해결할 수 있다.
map을 통해 몇 개 남았는지 확인해 주며 2개의 우선순위 큐를 사용하면 된다.