[Python][C++]7662번 우선순위 큐

문제

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

 

 

 

코드

1. Python

import sys
import heapq

input = sys.stdin.readline  # 빠른 입력을 위해 sys.stdin.readline 사용

# 테스트 케이스 수만큼 반복
for _ in range(int(input())):
    min_heap = []  # 최소 힙 (최소값을 빠르게 꺼내기 위함)
    max_heap = []  # 최대 힙 (최대값을 빠르게 꺼내기 위함, 음수로 저장하여 사용)
    visited = {}  # 각 숫자가 힙에 몇 번 들어갔는지 추적하기 위한 딕셔너리

    # 각 테스트 케이스의 명령어 수만큼 반복
    for _ in range(int(input())):
        op, n = input().split()  # 명령어와 숫자 입력 받기
        n = int(n)  # 숫자를 정수형으로 변환

        if op == 'I':  # 'I' 명령어: 삽입
            heapq.heappush(min_heap, n)  # 최소 힙에 삽입
            heapq.heappush(max_heap, -n)  # 최대 힙에 삽입 (음수로 저장)
            try:
                visited[n] += 1  # 이미 존재하는 숫자라면 개수 증가
            except:
                visited[n] = 1  # 처음 등장하는 숫자라면 개수 1로 초기화

        elif op == 'D':  # 'D' 명령어: 삭제
            if n == 1:  # 최대값 삭제
                # 최대 힙에서 유효하지 않은 값(이미 삭제된 값)을 제거
                while max_heap and not visited[-max_heap[0]]:
                    heapq.heappop(max_heap)

                if max_heap:  # 아직 남아있는 값이 있으면
                    visited[-heapq.heappop(max_heap)] -= 1  # 최대값을 제거하고 visited에서 감소

            elif n == -1:  # 최소값 삭제
                # 최소 힙에서 유효하지 않은 값(이미 삭제된 값)을 제거
                while min_heap and not visited[min_heap[0]]:
                    heapq.heappop(min_heap)

                if min_heap:  # 아직 남아있는 값이 있으면
                    visited[heapq.heappop(min_heap)] -= 1  # 최소값을 제거하고 visited에서 감소

    # 최종적으로 남아있는 힙에서 유효하지 않은 값들을 제거
    while max_heap and not visited[-max_heap[0]]:
        heapq.heappop(max_heap)
    while min_heap and not visited[min_heap[0]]:
        heapq.heappop(min_heap)

    # 남아있는 값 중에서 최대값과 최소값을 출력
    if min_heap and max_heap:
        print(-max_heap[0], min_heap[0])  # 최대값, 최소값 출력
    else:
        print("EMPTY")  # 힙이 비어있으면 "EMPTY" 출력

 

2. C++

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    int t;

    cin >> t;  // 테스트 케이스의 수 입력

    while (t--) {
        int k;
        cin >> k;  // 각 테스트 케이스에서 주어지는 명령의 수 입력

        priority_queue<int> maxHeap; // 최대 힙 (최대값을 빠르게 찾기 위함)
        priority_queue<int, vector<int>, greater<int>> minHeap; // 최소 힙 (최소값을 빠르게 찾기 위함)
        unordered_map<int, int> count; // 각 숫자의 삽입된 횟수를 저장하는 맵

        for (int i = 0; i < k; i++) {
            char cmd;
            int num;
            cin >> cmd >> num;  // 명령과 숫자 입력

            if (cmd == 'I') {  // 삽입 명령일 경우
                maxHeap.push(num);  // 최대 힙에 숫자 삽입
                minHeap.push(num);  // 최소 힙에 숫자 삽입
                count[num]++;  // 해당 숫자의 삽입 횟수 증가
            }
            else if (cmd == 'D') {  // 삭제 명령일 경우
                if (num == 1) { // 최대값 삭제 명령일 경우
                    while (!maxHeap.empty() && count[maxHeap.top()] == 0) {
                        maxHeap.pop(); // 이미 삭제된 값(횟수가 0인 값)은 무시
                    }
                    if (!maxHeap.empty()) {
                        count[maxHeap.top()]--;  // 최대값의 삽입 횟수를 감소
                        maxHeap.pop();  // 최대값 삭제
                    }
                }
                else if (num == -1) { // 최소값 삭제 명령일 경우
                    while (!minHeap.empty() && count[minHeap.top()] == 0) {
                        minHeap.pop(); // 이미 삭제된 값(횟수가 0인 값)은 무시
                    }
                    if (!minHeap.empty()) {
                        count[minHeap.top()]--;  // 최소값의 삽입 횟수를 감소
                        minHeap.pop();  // 최소값 삭제
                    }
                }
            }
        }

        // 최대 힙과 최소 힙에서 이미 삭제된 값들을 제거
        while (!maxHeap.empty() && count[maxHeap.top()] == 0) {
            maxHeap.pop();
        }
        while (!minHeap.empty() && count[minHeap.top()] == 0) {
            minHeap.pop();
        }

        // 결과 출력
        if (maxHeap.empty() || minHeap.empty()) {
            cout << "EMPTY" << endl;  // 힙이 비어있으면 "EMPTY" 출력
        }
        else {
            cout << maxHeap.top() << " " << minHeap.top() << endl;  // 최대값과 최소값 출력
        }
    }

    return 0;
}

 

 

풀이 

 

1. 이중 우선순위 큐:
   • 최댓값과 최솟값을 동시에 빠르게 찾고 삭제하기 위해서 두 개의 힙(최대 힙과 최소 힙)을 사용
   • 최대 힙은 최댓값을 빠르게 추출할 수 있고, 최소 힙은 최솟값을 빠르게 추출 가능
   • 삽입된 값은 두 힙에 모두 저장되고, 삭제 시 해당 힙에서만 삭제하는 방식으로 구현
2. 동기화:
   • 두 힙이 독립적으로 동작하기 때문에, 한쪽에서 삭제된 값이 다른 힙에도 반영되어야 함. 이를 위해 힙의 상태를 동기화하는 과정이 필요
   • 삭제 시 동기화를 위해 dict나 set을 사용하여 삽입된 요소들의 상태를 기록. 삭제된 요소는 다른 힙에서 유효하지 않은 상태로 처리
3. 구현 방법:
   • I n 연산 시 두 힙에 값을 삽입
   • D 1 연산 시 최대 힙에서 값을 제거하고, 이 값이 최소 힙에서 유효한 값인지 확인. 유효하지 않다면 최대 힙을 다시 조정
   • D -1 연산 시 최소 힙에서 값을 제거하고, 유효하지 않은 값이면 최소 힙을 다시 조정
   • 모든 연산이 끝난 후 힙이 비어있다면 "EMPTY"를 출력하고, 비어있지 않다면 각각 최댓값과 최솟값을 출력