[BOJ/백준 7662][C++] 이중 우선순위 큐

문제

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

백준 7662

 

문제 내용

I연산은 뒤에 오는 수를 이중 우선순위 큐에 "삽입"하는 연산이다.

D -1 연산은 최솟값을 이중 우선순위 큐에서 "삭제"하는 연산이고, D 1 연산은 최댓값을 이중 우선순위 큐에서 "삭제"하는 연산이다.

이중 우선순위 큐에 원소가 없을 때 D연산이 들어오면, 그냥 무시한다.

이중 우선순위 큐에는 같은 원소가 여러번 들어갈 수 있다.

우리는 모든 연산이 끝난 후, 비어있다면 EMPTY를, 그렇지 않으면 최솟값과 최댓값을 출력하면 된다.

 

문제 풀이

문제 이름은 이중 "우선순위 큐" 이지만, 문제를 잘 보면, 최대/최솟값을 모두 찾아야 함을 알 수 있다.

따라서 heap(priority_queue)가 아니라 set을 사용할 예정이다.

또한, 값이 중복으로 들어갈 수 있기 때문에 multiset을 사용했다.

이 문제는 자료구조만 적절히 고른다면 쉽게 해결할 수 있다.

 

코드

#include <iostream>
#include <set>

using namespace std;

void solution() {
    int k;
    cin >> k;

    string ch, n;
    multiset<int> ss;
    while (k--) {
        cin >> ch >> n;

        if (ch == "I") // 삽입 연산
            ss.insert(stoi(n));

        else { // D 삭제 연산
            if (ss.empty())
                continue;

            if (n == "1") {
                ss.erase(--ss.end());
            } else {
                ss.erase(ss.begin());
            }
        }
    }

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int testCase;
    cin >> testCase;
    while (testCase--) {
        solution();
    }
}