Baekjoon7662 - 이중 우선순위큐 (Python)

백준 사이트 7662 - 이중 우선순위큐 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

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

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

solved.ac class 3 문제입니다.

---

☑️ 4. 생각한 것들

• 당연하게도 brute하게 접근하면 시간초과가 나옵니다.
• max,min에 대한 heap을 가지고 있어야하는데, 각각 데이터를 뺄때나 더할때나 동일한 값을 가지고 있어야합니다. 이것을 해결하는게 이 문제의 핵심입니다.
• 중복으로 값이 들어올 수도 있으므로, dictionary를 통하여 상태를 관리합니다.
• 뺄때의 while문은 이전 루프에서 루트값을 제거한 경우를 해결하기 위해 넣은것입니다. 예를들면 max_heap,min_heap이 7,7,-8 두 개의 값을 가지고 있고 D 1라는 두번의 명령으로 빼면 max_heap은 -8만 남은 값이 되고, dic[7] = 0이 될 것입니다. 만약 여기서 D -1 명령어 두 번을 통해 최소값을 두 번 뺀다고 하면 처음에는 min_heap에는 여전히 7,7이라는 숫자가 남게 되는데, 두 번째 명령어를 실행할땐 dic[root]는 0인데, 7,7이라는 숫자가 있기에 그 차이만큼 계속 빼주는 것입니다.
• 마지막 while문도 동일한 방식으로 생각하면 됩니다.

---

5. code

from heapq import heappop, heappush
from sys import stdin


def solution() -> None:
    t = int(stdin.readline())
    for i in range(t):
        command_count = int(stdin.readline())
        max_heap = []
        min_heap = []
        dic = {}
        for _ in range(command_count):
            command, data = map(str, stdin.readline().split())
            data = int(data)
            if command == 'I':
                heapq.heappush(max_heap, -data)
                heapq.heappush(min_heap, data)
                if data in dic:
                    dic[data] += 1
                else:
                    dic[data] = 1
            else:
                if data == -1:
                    while min_heap:
                        root = heappop(min_heap)
                        if dic[root] != 0:
                            dic[root] -= 1
                            break
                else:
                    while max_heap:
                        root = -heapq.heappop(max_heap)
                        if dic[root] != 0:
                            dic[root] -= 1
                            break
        while max_heap and dic[-max_heap[0]] == 0:
            heapq.heappop(max_heap)
        while min_heap and dic[min_heap[0]] == 0:
            heapq.heappop(min_heap)
        if max_heap:
            print(-max_heap[0], min_heap[0])
        else:
            print("EMPTY")


solution()

---

6. 후기

• 어렵습니다.

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.