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

문제 링크 : https://www.acmicpc.net/problem/7662

극한의 우선순위 큐 (= 힙) 사용문제. 힙을 4개 사용해서 풀었다. 최댓값과 최솟값을 둘 다 pop 할 수 있는 이중 힙을 만들어야 되기 때문에, 먼저 minHeap maxHeap 두 개를 만들었다.

삽입 연산 "I" 를 실행할때는 minHeap maxHeap 두 군데에 다 삽입해준다. 그리고 최댓값 삭제 "D 1" 을 실행할때는 maxHeap 에서 pop 하고, 삭제한 값을 maxPop 에 삽입한다. 이 때 maxPop 은 최소힙으로 설정해야된다. 그래야 나중에 minHeap 에서 pop 연산이 일어날 때, 이미 삭제된 값인지 확인할 수 있기 때문이다. 반대로 minPop 은 최대 힙으로 만들어주면 된다.

파이썬의 heapq 는 기본 값이 최소 힙이기 때문에, 최대 힙으로 사용할 때 음수 값으로 바꿔서 사용하는 것도 잊지 말아야된다.

파이썬 코드

import heapq
import sys
T = int(sys.stdin.readline())


def program():
    K = int(sys.stdin.readline())
    minHeap, maxHeap = [],  []
    minPop, maxPop = [],  []

    for _ in range(K):
        cmd = sys.stdin.readline().split()
        # 삽입
        if cmd[0] == 'I':
            heapq.heappush(minHeap, int(cmd[1]))
            heapq.heappush(maxHeap, -int(cmd[1]))
        # 삭제
        elif cmd[0] == 'D':
            # 최댓값 삭제
            if cmd[1] == '1':
                # 비어있으면 무시
                if not maxHeap:
                    continue
                # 이미 minHeap 에서 삭제된 값들은 건너뜀
                while (maxHeap and minPop) and (-maxHeap[0] == -minPop[0]):
                    heapq.heappop(maxHeap)
                    heapq.heappop(minPop)
                # 건너뛰어 보니 비어있으면 무시
                if not maxHeap:
                    continue
                x = heapq.heappop(maxHeap)
                heapq.heappush(maxPop, -x)
            # 최솟값 삭제
            elif cmd[1] == '-1':
                # 비어있으면 무시
                if not minHeap:
                    continue
                # 이미 maxHeap 에서 삭제된 값들은 건너뜀
                while (minHeap and maxPop) and (minHeap[0] == maxPop[0]):
                    heapq.heappop(minHeap)
                    heapq.heappop(maxPop)
                # 건너뛰어 보니 비어있으면 무시
                if not minHeap:
                    continue
                x = heapq.heappop(minHeap)
                heapq.heappush(minPop, -x)

    # 마무리 하고 이중 힙에 남아있는 최대 최솟값 출력
    maxV, minV = 0, 0
    while (maxHeap and minPop) and (maxHeap[0] == minPop[0]):
        heapq.heappop(maxHeap)
        heapq.heappop(minPop)
    if not maxHeap:
        print("EMPTY")
        return
    maxV = -maxHeap[0]
    while (minHeap and maxPop) and (minHeap[0] == maxPop[0]):
        heapq.heappop(minHeap)
        heapq.heappop(maxPop)
    minV = minHeap[0]
    print(maxV, minV)
    return


for _ in range(T):
    program()