문제
이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.
정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.
문제 풀이
이 문제의 중요한 점은 아래 두가지라고 생각한다.
-
파이썬의
heapq는 최소힙만 지원하기 때문에 최대힙은 따로 구현해주어야 한다.- 최대힙 구현을 위해 삽입 시 입력받은 n 에 -1을 곱하고 결과값을 출력 시에는 -1을 다시 곱한 후 출력
-
최대힙, 최소힙을 동기화 시켜주어야 한다.
-
힙에 push 할 때 입력받은 값 n 과 반복문이 몇 번 수행되었는지 가리키는 변수 i 를 튜플 형태로 함께 넣어줌 (파이썬의 튜플 비교연산은 첫 번째 원소를 기준으로 판단하기 때문에 힙의 구동에 영향 X)
-
삭제 연산 시 id를 기준으로 해당 노드가 다른 힙에서 삭제된 노드인지 확인하기 위해
deleted플래그 리스트 사용-
이미 삭제된 노드인 경우 삭제되지 않은 노드가 나올 때까지 모두 버림
-
삭제 대상 노드 등장 시 삭제
-
-
모든 연산이 끝난 후에도 남아있는 동기화 되지 않은 노드가 있을 수 있기 때문에 각 힙의 원소의
id에 해당하는deleted값이True로 되어있는 값들은 버려주어 동기화 시킴
-
# BOJ 7762 골드4
import sys
import heapq
def sync(arr):
while arr and deleted[arr[0][1]]:
heapq.heappop(arr)
input = sys.stdin.readline
T = int(input())
for test_case in range(T):
max_heap = []
min_heap = []
k = int(input())
deleted = [True] * k
for i in range(k):
s, num = input().split()
if s == "I":
heapq.heappush(max_heap, (-1 * int(num), i))
heapq.heappush(min_heap, (int(num), i))
deleted[i] = False
else:
if num == "1":
sync(max_heap)
if max_heap:
deleted[max_heap[0][1]] = True
heapq.heappop(max_heap)
elif num == "-1":
sync(min_heap)
if min_heap:
deleted[min_heap[0][1]] = True
heapq.heappop(min_heap)
sync(max_heap)
sync(min_heap)
if min_heap and max_heap:
print(-max_heap[0][0], min_heap[0][0])
else:
print("EMPTY")