우선순위 큐

이중 우선순위 큐

문제의 핵심 : 방문 처리 & 동기화
이중 우선순위 큐이기 때문에 최대힙과 최소힙을 모두 사용해서 D가 1이면 최대힙에서 삭제, -1이면 최소힙에서 삭제한다. 그런데 이때 필요한 것이 동기화이다. 최대힙에서 삭제 된것을 최소힙에서도 똑같이 삭제하는 것이다. 그래서 필요한 것이 방문처리이다.

import sys
import heapq
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	max_heap = []
	min_heap = []
	visited = [False] * n 
    # 
	for i in range(n):
		x, y = input().split()
		if x == 'I': # 집어넣고, 해당 수 방문 처리 
			heapq.heappush(min_heap, [int(y), i])
			heapq.heappush(max_heap, [-int(y), i])
			visited[i] = True # 이 수는 최소힙, 최대힙에 모두 있다. 
		else:
			if int(y) == 1:
            			# 최대힙이 있다면 최대힙 삭제 , 그리고 삭제한 수는 이제 삭제해야함 
            			# 최소힙에서 방문한 수는  최대힙에서도 그 숫자 삭제해주기 
				while max_heap and visited[max_heap[0][1]] == False:
					heapq.heappop(max_heap)
				if max_heap:
					visited[max_heap[0][1]] = False
					heapq.heappop(max_heap)
			else:
				while min_heap and visited[min_heap[0][1]] == False:
					heapq.heappop(min_heap)
				if min_heap:
					visited[min_heap[0][1]] = False
					heapq.heappop(min_heap)
     	# 모두 다 삭제 됐다면 'EMPTY'출력
	if True not in visited:
		print('EMPTY')
       #여기서도 마지막으로 동기화해주고
       # 최대, 최소 값 출력
	else:
		while max_heap and visited[max_heap[0][1]] == False:
			heapq.heappop(max_heap)
		while min_heap and visited[min_heap[0][1]] == False:
			heapq.heappop(min_heap)
		print(-max_heap[0][0], min_heap[0][0])