7662 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

<아이디어>

처음에 이 문제를 접했을 때에는 문제이름이 이중 우선순위 큐여서 우선순위가 다른 priority_queue를 2개 선언해서 두개로 돌렸는데 다시 생각해보니 말도 안되는 방법이었다...

 

그래서 map을 사용해서 value 값을 counting 용도로 쓰면서 naive하게 진행.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        int k, num;
        map<int, int> mp;
        cin>>k;
        char order;
        for(int i=0;i<k;i++)
        {
            cin>>order>>num;
            if(order=='I') mp[num] += 1;
            if(order=='D')
            {
                map<int, int>::iterator it;
                if(mp.empty()) continue;
                if(num==1)
                {
                    it = mp.end();
                    it--;
                    it->second -= 1;
                    if(it->second==0) mp.erase(it);
                }
                if(num==-1)
                {
                    it = mp.begin();
                    it->second -= 1;
                    if(it->second==0) mp.erase(it);
                }
            }    
        }
        if(mp.empty()) cout<<"EMPTY\n";
        else
        {
            map<int, int>::iterator a = mp.begin(), b = mp.end();
            b--;
            cout<<b->first<<' '<<a->first<<endl;
        }
    }
 
    return 0;
}