백준, BOJ, 7662번, 이중 우선순위 큐 C++ [CPP] ★★

두개의 큐를 쓰면 되지 않을까??? 생각이었지만

예외처리가 꽤나 까다로웠다.

 

 

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

---

 

여러가지 방법이 있겠지만

나는 쉬운 방법으로 풀었다.

MultiSet 자체가 무엇을 위해 만들어졌냐고 하면..?

Set이라는 것이 집합이라 중복을 허용하지 않지만..

이 친구는 key의 중복을 허용해서 유용하게 이 문제에 쓰였다.

 

중복이 허용되는 Set이라고 보면 된다.

자동정렬 + key,value 형태라고 보면 된다.

 

#맞는 풀이

#include <bits/stdc++.h>

using namespace std;

int tc;


int main(){
    cin>>tc;
    while(tc--){
        int k;
        cin >> k;
        
        
        //1. ordered된 multi_set으로  중복도 포함된 set을 만들자.
        multiset<int> setQ;
        //2. 최댓값과 최솟값을 둘 다 이용하려면 큐를 2개 만듬.
        //priority_queue<int, vector<int> less<int>> maxq;
        //priority_queue<int, vector<int> grreater<int>> minq;
        while(k--){
            char x;
            int n;
            cin >> x;
            cin >> n;
            //I 라면 삽입
            if(x == 'I'){
                setQ.insert(n);
                //maxq.push(n);
                //minq.push(n);
            }
            //D 라면 삭제
            else if(x == 'D' ){
                if(n == 1 && !setQ.empty()){
                    auto it = setQ.end();
                    it--;
                    setQ.erase(it);
                    //if(!maxq.empty())
                    //    maxq.pop();
                }else if(n == -1  && !setQ.empty()){
                    setQ.erase(setQ.begin());
                    //if(!minq.empty())
                    //    minq.pop();
                }
            }
        }
        if(setQ.empty()){
            cout << "EMPTY";
        }
        else{
            auto maxIt = setQ.end();
            maxIt--;
            cout << *(maxIt) << ' ' << *(setQ.begin());
        }
        
        cout << '\n';

    }
    return 0;
}