백준 7662번(이중 우선순위 큐) C++ 풀이

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
priority_queue<int, vector<int>, greater<int>> min_queue;
priority_queue<int, vector<int>, less<int>> max_queue;
map<int, int> test;
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        test.clear();
        while (min_queue.empty() == 0)
        {
            min_queue.pop();
        }
        while (max_queue.empty() == 0)
        {
            max_queue.pop();
        }

        int coun;
        cin >> coun;

        for (int j = 0; j < coun; j++)
        {
            char a;
            int b;
            cin >> a >> b;

            if (a == 'I')
            {
                min_queue.push(b);
                max_queue.push(b);
                if (test.count(b) == 0)
                {
                    test[b] = 1;
                }
                else
                {
                    test[b]++;
                }
            }
            if (a == 'D')
            {

                if (b == 1)
                {

                    while (!max_queue.empty() && test[max_queue.top()] == 0)
                    {
                        max_queue.pop();
                    }
                    if (max_queue.empty() == 1)
                    {
                        continue;
                    }
                    // cout << max_queue.top();
                    test[max_queue.top()]--;
                    max_queue.pop();
                }
                if (b == -1)
                {

                    while (!min_queue.empty() && test[min_queue.top()] == 0)
                    {
                        min_queue.pop();
                    }
                    if (min_queue.empty() == 1)
                    {
                        continue;
                    }
                    test[min_queue.top()]--;
                    // cout << min_queue.top() << "s";
                    min_queue.pop();
                }
            }
        }

        while (!max_queue.empty() && test[max_queue.top()] == 0)
        {
            max_queue.pop();
        }
        while (!min_queue.empty() && test[min_queue.top()] == 0)
        {
            min_queue.pop();
        }

        if (max_queue.empty() == 1)
        {
            cout << "EMPTY\n";
        }
        else
        {
            cout << max_queue.top() << " " << min_queue.top() << "\n";
        }
    }
}

간만에 풀어본 조금 어려운 문제였다. 일단, 이중 우선순위 큐를 구현하는것을 max_queue와 min_queue 두개를 만들어서 연산하는 식으로 계산하였다. 그리고, dp의 visited 개념을 이용하여, test라는 map을 만들어, 이 수가 다른 queue에서 제거되었는지 안제거되었는지 지속해서 체크하는 로직을 만들어주었다. 이 로직을 통해 다른 큐에서 제거된 수라면, pass 하는식으로 문제를 해결할 수 있었다. 사실 map이 아닌 배열을 사용하려 했으나, 배열의 크기가 100만을 넘어가기에 map을 통하여 구현하였다.