문제 설명
•
이중 우선순위 큐를 사용하여 주어진 연산을 수행한 뒤, 큐가 비어있으면 [0, 0], 비어있지 않으면 [최댓값, 최솟값]을 반환하는 문제
명령어 | 수신 탑(높이) |
I 숫자 | 큐에 주어진 숫자를 삽입합니다. |
D 1 | 큐에서 최댓값을 삭제합니다. |
D -1 | 큐에서 최솟값을 삭제합니다. |
예제 입력/출력
operations | return |
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"] | [0,0] |
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] | [333, -45] |
제약 조건
•
문제 풀이
•
이 문제는 최댓값과 최솟값을 효율적으로 삽입 및 삭제해야 하는 문제이므로 최소 힙과 최대 힙을 함께 사용하는 것이 핵심이다.
•
최소, 최대 힙
◦
파이썬의 heapq는 최소 힙만 제공하므로, 최대 힙을 구현하려면 음수를 활용해야한다.
▪
최소 힙 (min_hq) → 원래 숫자 그대로 저장
▪
최대 힙 (max_hq) → 음수로 변환 후 저장
•
동기화 문제 해결
◦
각 힙은 독립적으로 동작하기 때문에, 한쪽 힙에서 삭제된 값이 다른 힙에는 그대로 남아 있는 문제가 발생한다.
◦
예를 들어, max_heap에서 최댓값을 삭제했는데, min_heap에는 여전히 존재할 수 있다.
◦
따라서, 딕셔너리(entry_map)를 활용하여 각 숫자가 현재 큐에 몇 개 있는지를 같이 관리해준다.
풀이 코드
import heapq
from collections import defaultdict
def solution(operations):
min_heap = [] # 최소 힙
max_heap = [] # 최대 힙 (음수로 저장)
entry_map = defaultdict(int) # 실제 존재하는 값 관리
for op in operations:
if op == "D 1": # 최댓값 삭제
while max_heap:
max_val = -heapq.heappop(max_heap)
if entry_map[max_val] > 0: # 유효한 값인지 확인
entry_map[max_val] -= 1
break
elif op == "D -1": # 최솟값 삭제
while min_heap:
min_val = heapq.heappop(min_heap)
if entry_map[min_val] > 0: # 유효한 값인지 확인
entry_map[min_val] -= 1
break
else:
num = int(op.split()[1])
heapq.heappush(min_heap, num)
heapq.heappush(max_heap, -num)
entry_map[num] += 1
# 남아있는 값 정리 (유효한 최댓값/최솟값 찾기)
while min_heap and entry_map[min_heap[0]] == 0:
heapq.heappop(min_heap)
while max_heap and entry_map[-max_heap[0]] == 0:
heapq.heappop(max_heap)
# 결과 출력
if not min_heap or not max_heap:
return [0, 0]
return [-max_heap[0], min_heap[0]]
Python
복사