백준 07662 - 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

 

고려사항

• map 활용.
• map은 key를 기준으로 정렬을 해준다.
• insert 시에 map에 존재하지 않으면 (num, 1)로 삽입,
  이미 존재하면 m[num] 의  value 를 +1 해준다.
• delete 는 map의 사이즈가 0이 아닐 시에만 연산을 진행하고,
  연산이 -1 이면, m.begin() 의 value를,
  연산이 1 이면, --m.end() 의 value를 확인해보고, 1이면 삭제를, 2이상이면 -1을 해준다.
  m.end()는 m의 마지막 원소 다음을 가르킨다 => --m.end() 는 마지막 원소를 가르킨다 => 키가 가장 큰 값!

 

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int t, n, num;
    char op;
    cin>>t;
    for(int i=0;i<t;++i){
        map<int, int> m;

        cin>>n;
        for(int j=0;j<n;++j){
            cin>>op>>num;
            if(op == 'I'){
                if(m.find(num) != m.end()){
                    ++m[num];
                }else{
                    m[num] = 1;
                }
            }else{
                if(m.size() != 0){
                    if(num == -1){
                        if(m.begin()->second == 1){
                            m.erase(m.begin());
                        }else{
                            --m.begin()->second;
                        }
                    }else{
                        if((--m.end())->second == 1){
                            m.erase(--m.end());
                        }else{
                            --(--m.end())->second;
                        }
                    }
                }
            }
        }

        if(m.size() == 0){
            cout<<"EMPTY\n";
        }else{
            cout<<(--m.end())->first<<" "<<m.begin()->first<<"\n";
        }
    }

    return 0;
}