[백준-7662] 이중 우선순위 큐 / Python

7662번: 이중 우선순위 큐

import sys
import heapq

input = sys.stdin.readline

answer = []
for _ in range(int(input())):
    visited = [False] * 1000001
    minH, maxH = [], []
    for i in range(int(input())):
        s = input().split()
        if s[0] == "I":
            heapq.heappush(minH, (int(s[1]), i))
            heapq.heappush(maxH, (-int(s[1]), i))
            visited[i] = True
        elif s[1] == "1":
            while maxH and not visited[maxH[0][1]]:
                heapq.heappop(maxH)
            if maxH:
                visited[maxH[0][1]] = False
                heapq.heappop(maxH)
        else:
            while minH and not visited[minH[0][1]]:
                heapq.heappop(minH)
            if minH:
                visited[minH[0][1]] = False
                heapq.heappop(minH)

    while minH and not visited[minH[0][1]]:
        heapq.heappop(minH)
    while maxH and not visited[maxH[0][1]]:
        heapq.heappop(maxH)

    answer.append(f"{-maxH[0][0]} {minH[0][0]}" if maxH and minH else "EMPTY")

print("\n".join(answer))

 

해설

파이썬에서 힙은 최소힙만 지원하기 때문에 최대힙도 따로 구현을 해줘야한다. 이 부분은 -1을 곱해주는 것으로 해결할 수 있다. 이제 최소힙과 최대힙의 동기화가 필요하다. 이는 인덱스를 활용해 해결할 수 있다. 값과 인덱스를 튜플로 리스트에 넣어준다. 인덱스를 기준으로 해당 노드가 다른 힙에서 삭제된 노드인지 아닌지를 판단하고, 이미 삭제된 노드라면 삭제되지 않은 노드가 나올 때까지 모두 버린다. 삭제 대상 노드가 등장하면 삭제한다. 이를 위해 각 인덱스별로 활성상태를 기록하는 플래그 리스트 visited를 사용한다.

연산이 모두 끝난 후에도 쓰레기 노드들이 남아있을 수 있다. 이 때문에, 결과를 내기 전 쓰레기 노드를 모두 비우고 각 힙의 첫번째 값을 출력한다.

 

너무 어려운 문제였다........😥