[BOJ, Python] 7662 - 이중 우선순위 큐 ( with Heap )

7662번: 이중 우선순위 큐

파이썬은 힙 라이브러리가 내장되어 있어서 따로 구현없이 편히 풀 수 있다. 다만 최대, 최소, 절댓값 힙 등은 힙에 push를 해주는 과정에서 살짝 변형만 해주면 되지만 이중 우선순위 큐는 좀 더 복잡한 코드 작성을 요구한다.

 

기본적인 틀은 이러하다.

1. 최대, 최소 힙을 담을 리스트를 각각 하나씩 초기화한다.

2. 값을 추가할 때 최소는 그대로, 최대는 요소에 -1을 곱해준다.

3. 값에는 튜플 형태로 (값, id) 구성해 추가해주고, 지우는 과정에서 각각의 리스트에서 중복되는 값을 같이 없애준다.

import heapq
import sys

input = sys.stdin.readline
size = int(input())

# 최소, 최대 힙
min_heap = []
max_heap = []

# 각각의 리스트에서 해당 요소가 삭제됐는지 판단할 수 있는 식별 리스트
id = [0] * 1000000

# 배열이 비어있지 않았는데 최대나, 최솟값의 id가 0이라면
# 이미 반대쪽 리스트에서 삭제되었다는 의미, 따라서 삭제
def synclen(arr):
    while arr and id[arr[0][1]] == 0:
        heapq.heappop(arr)

for idx in range(size):
    p, i = map(str, input().rstrip().split())
    
    if p == "I":
    	# 각각의 값을 추가해주고 해당 시행의 인덱스를 id로 사용
        heapq.heappush(min_heap, (int(i), idx))
        heapq.heappush(max_heap, (-int(i), idx))
        id[idx] = 1
    else:
    	# 각각의 경우에서 중복되는 값 삭제
        # 해당 리스트가 비어있지 않다면
        # id값을 0으로 바꿔주어 삭제했음을 표시, 최대 or 최소 제거
        if i == "-1":
            synclen(min_heap)
            if min_heap:
                id[min_heap[0][1]] = 0
                heapq.heappop(min_heap)
        else:
            synclen(max_heap)
            if max_heap:
                id[max_heap[0][1]] = 0
                heapq.heappop(max_heap)
# 한 번 더 체크
synclen(max_heap)
synclen(min_heap)

# 비어있으면 "EMPTY" 출력, 아니면 최대/최소 출력
if not max_heap:
    print("EMPTY")
else:
    print(-1 * max_heap[0][0], min_heap[0][0])