7662번 이중 우선순위 큐

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

우선순위 큐와 map을 이용하여 풀었다.

가장 먼저 maxQ와 minQ를 모두 만들어 데이터를 넣은 후 데이터를 삭제 할땐 maxQ와 minQ모두 삭제 해야 하므로 map을 이용하여 if(map == 0)일때 데이터를 삭제해줬다.

 

#include <bits/stdc++.h>
#define l long long
#define INF 2e9
#define p pair<int,int>
#define vc vector<int>
#define F first
#define S second
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int t,k,n;
    char c;
    cin >> t;

    while(t--){
        unordered_map<int,int> check;
        priority_queue<int,vc,greater<>> MinQ; // 오름 차순
        priority_queue<int,vc,less<>> MaxQ; // 내림차순

        cin >> k;

        for(int i=0;i<k;i++) {
            cin >> c >> n;

            if (c == 'I') {
                check[n]++;
                MinQ.push(n);
                MaxQ.push(n);
            }
            else {
                if (n == 1) {
                    while(!MaxQ.empty() && check[MaxQ.top()] == 0) MaxQ.pop();

                    if(MaxQ.empty()) continue;
                    check[MaxQ.top()]--, MaxQ.pop();
                }
                else if (n == -1) {

                    while(!MinQ.empty() && check[MinQ.top()] == 0) MinQ.pop();

                    if(MinQ.empty()) continue;
                    check[MinQ.top()]--, MinQ.pop();
                }
            }
        }
        while(!MaxQ.empty() && check[MaxQ.top()] == 0) MaxQ.pop();
        while(!MinQ.empty() && check[MinQ.top()] == 0) MinQ.pop();

       if(MaxQ.empty() && MinQ.empty()) cout << "EMPTY\n";
       else cout << MaxQ.top() << " " << MinQ.top() << "\n";

    }
}