[백준] 7662 파이썬(python) : 이중 우선순위 큐 - 이중 큐 동기화

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

 

처음엔 heap을 하나 생성해서 최대일때는 어떻게 빼주면 좋을까 고민하다가 해법이 떠오르지 않아 블로그를 찾아봤는데 이중heap을 만드는걸 보고 놀랐다. 동시에 입력을 받고 동기화를 True, False의 형태로 받아주는것인데 대단한 방법이다.

 

import sys, heapq
t = int(sys.stdin.readline())
for _ in range(t):
    k = int(sys.stdin.readline())
    min_heap, max_heap = [], [] #1
    visit = [False]*k #2
    for idx in range(k):
        cmd = sys.stdin.readline().split() #3
        if cmd[0] == 'I': #4
            heapq.heappush(min_heap, (int(cmd[1]), idx))
            heapq.heappush(max_heap, (-int(cmd[1]), idx))
            visit[idx] = True
        elif cmd[0] == 'D': #5
            if cmd[1] == '-1': #6
                while min_heap and not visit[min_heap[0][1]]: #7
                    heapq.heappop(min_heap)
                if min_heap: #8
                    visit[min_heap[0][1]] = False
                    heapq.heappop(min_heap)
            elif cmd[1] == '1': #9
                while max_heap and not visit[max_heap[0][1]]: #10
                    heapq.heappop(max_heap)
                if max_heap: #11
                    visit[max_heap[0][1]] = False
                    heapq.heappop(max_heap)
    while min_heap and not visit[min_heap[0][1]]: #12
        heapq.heappop(min_heap)
    while max_heap and not visit[max_heap[0][1]]:
        heapq.heappop(max_heap)
    if min_heap and max_heap: #13
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print('EMPTY')

 

#1 : 최소 힙과 최대 힙 리스트 생성

#2 : 동기화를 위한 리스트 생성

#3 : 명령 입력

#4 : 입력값의 첫 요소가 'I'인 경우 최소힙에는 그냥 최대힙에는 음수로 값을 인덱스와 함께 넣어줌

#5 : 입력값의 첫 요소가 'D'인 경우 

#6 : 최소 값을 제거해야하는 명령일때 

#7 : 이미 최대 힙에서 제거되어버린 노드일때 삭제되지 않은 노드가 나올떄까지 heappop()

최대 힙에서 제거된 노드는 True에서 False로 바뀌어 있음

#8 : 최소 힙의 heap[0]의 True를 False로 바꾸고 heap[0]을 삭제

#9 : 최대 값을 제거해야하는 명령일때

#10 : 이미 최소 힙에서 제거되어버려 인덱스값이 False가 된 노드는 모두 제거

#11 : 현재 최대 힙의 가장 큰 값의 인덱스 값을 False로 바꾸고 heappop()

#12 : 최소 힙과 최대 힙에 상대방의 힙에서는 제거되었지만 남아있는 쓰레기 노드를 제거

#13 : 마지막에 힙에 원소가 남아 있으면 최대 값과 최소 값 출력, 원소가 없다면 EMPTY출력