백준 7662번 [이중 우선순위 큐](C++) -yes6686- 티스토리

백준 문제 풀이: 7662 [이중 우선순위 큐]

---

문제 링크: https://www.acmicpc.net/problem/7662

문제 설명:

이중 우선순위 큐는 다음과 같은 연산을 지원합니다:

• I n: 정수 n을 삽입합니다.
• D 1: 큐에서 최댓값을 삭제합니다.
• D -1: 큐에서 최솟값을 삭제합니다.

명령이 끝난 뒤 큐가 비어 있으면 "EMPTY"를 출력하고, 비어 있지 않으면 최댓값과 최솟값을 출력합니다.

입력 조건:

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 ≤ T ≤ 100)
• 각 테스트 케이스는 정수 연산의 개수 k가 주어지며, (1 ≤ k ≤ 1,000,000)
• 정수 n의 절댓값은 2³¹-1 이하입니다.

출력 조건:

• 각 테스트 케이스에 대해 큐가 비어 있으면 "EMPTY"를 출력합니다.
• 큐가 비어 있지 않으면 최댓값과 최솟값을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <set>
using namespace std;

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

    int T;
    cin >> T;

    while (T--) {
        int k;
        cin >> k;

        multiset<int> ms;

        while (k--) {
            char cmd;
            int n;
            cin >> cmd >> n;

            if (cmd == 'I') {
                ms.insert(n); // 삽입
            } else if (cmd == 'D') {
                if (!ms.empty()) {
                    if (n == 1) {
                        // 최댓값 삭제
                        ms.erase(prev(ms.end()));
                    } else if (n == -1) {
                        // 최솟값 삭제
                        ms.erase(ms.begin());
                    }
                }
            }
        }

        if (ms.empty()) {
            cout << "EMPTY\n";
        } else {
            cout << *prev(ms.end()) << ' ' << *ms.begin() << '\n';
        }
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 `multiset` 자료구조를 사용하여 이중 우선순위 큐를 구현합니다.

• 삽입 연산:
  • `multiset`에 정수 n을 삽입합니다.
• 삭제 연산:
  • `D 1`: 최댓값은 `prev(ms.end())`로 접근하여 삭제합니다.
  • `D -1`: 최솟값은 `ms.begin()`으로 접근하여 삭제합니다.
• 결과 출력:
  • 비어 있으면 "EMPTY"를 출력합니다.
  • 비어 있지 않으면 최댓값과 최솟값을 출력합니다.

시간 복잡도 분석:

• 삽입/삭제: O(log k).
• 최댓값/최솟값 접근: O(1).
• 최악의 경우 O(k log k)이며, 제한 내에서 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

출력:
EMPTY
333 -45

명령에 따라 이중 우선순위 큐가 올바르게 동작하며 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!