#7662 백준 이중 우선순위 큐 C++

 

백준 7662 번 이중 우선순위 큐 문제이다.

 

우선순위 큐의 성질을 문제에 적용시킨 것인데,

우선순위 큐와 다른 것은 가장 큰 값과, 가장 작은 값이 모두 손쉽게 삭제가 가능 하다는 점이다.

 

이 문제에서 주어지는 k값의 범위가 10000정도만 되어도 list를 고려해 볼 수 있었지만,

범위가 넓은 관계로 다른 컨테이너를 사용해야한다.

 

여기서 사용할 수 있는 컨테이너는 map과 multiset을 사용할 수 있다.

 

map을 사용하면, 첫 번째 인자는 값 자체를 넣어주고, 두 번째 인자는 값의 개수로 설정해서

동일한 key값이 삭제될 경우 두 번째 인자의 값을 줄이는 식의 풀이를 할 수 있다.

 

multiset을 사용하면 key값의 개수를 일일이 줄여줄 필요가 없기 때문에 map으로 구현하는 것 보다 쉽게 구현할 수 있다.

 

아래는 코드 C++을 사용한 코드 전문이다.

 

#include <iostream>
#include <set>

using namespace std;


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

    int t;
    cin >> t;
    while(t--) {
        multiset<int> ms;
        int k;
        cin >> k;
        while(k--) {
            char c;
            int x;
            cin >> c >> x;

            if(c == 'I') {
                ms.insert(x);
            }
            else if(c == 'D' && !ms.empty()) {
                if(x == 1)
                    ms.erase(--ms.end());
                else
                    ms.erase(ms.begin());
            }
        }
        if(!ms.empty()) {
            cout << *(--ms.end()) << ' ' << *ms.begin() << "\n";
        } else
            cout << "EMPTY" << "\n";

    }
    return 0;
}