백준 g4 7662 이중 우선순위 큐 c++

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

7662번: 이중 우선순위 큐

 

문제

우선순위 큐가 있다. 저장된 정수 값 자체가 우선순위라고 친다.

동일한 정수를 삽입 가능하다. 

 

테스트케이스의 개수 T가 주어진다.

각각의 T에 대해 연산의 개수인 K가 주어진다. 이후로 연산 K개가 주어진다.

연산은 Insert와 Delete 2종류가 존재한다.

Insert는 "I 숫자"로 주어지며 해당 수를 Q에 삽입하낟.

Delete는 "D -1" 또는 "D 1"로 주어진다. -1일 경우에는 최솟값을 삭제, 1일 경우에는 최댓값을 삭제한다. 

만약 Q가 비어있는데 D 연산이 주어지면 그 연산은 무시한다.

 

K개의 연산이 모두 끝난 후 Q에 존재하는 최댓값과 최솟값을 출력한다. Q가 비어있다면 EMPTY를 출력한다.

 

풀이

삽입/삭제가 굉장히 빈번하고, 최댓값과 최솟값 또한 자주 계산해야한다.

문제 자체는 어렵지 않으나 자료구조를 잘 골라야 한다.

 

이전에 배운 hash는 삽입/삭제는 매우 빨리 할 수 있지만 최댓값과 최솟값을 찾기 어렵다. 삽입/삭제/최댓값/최솟값 모두 lgN인 set(이진 검색 트리)를 사용해보자

 

여기서 set의 iterator는 중위 순회 순서대로이므로, 결국 오름차순으로 정렬되어있다는 것이 큰 장점이다. 최댓값은 tree.end()의 앞, 최솟값은 tree.begin()으로 구하면 된다.

 

+) erase안은 원소의 값 뿐만 아니라 iterator도 들어갈 수 있다.

 

전체 코드

/*boj g4 7662 이중 우선순위 큐*/
#include <iostream>
#include <set>
#define MAXN 105
using namespace std;

int T, K;
multiset<int> Q;
char a;
int num;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> K;
        Q.clear();
        while (K--) {
            cin >> a >> num;

            if (a == 'I') {
                Q.insert(num);
            } else if (a == 'D') {
                if (Q.empty())
                    continue;
                else if (num == -1) {
                    Q.erase(Q.begin());
                } else if (num == 1) {
                    Q.erase(--Q.end());
                }
            }
        }

        if (Q.empty())
            cout << "EMPTY"
                 << "\n";
        else {
            cout << *(--Q.end()) << " " << *Q.begin() << "\n";
        }
    }
}