[프로그래머스 코딩테스트 고득점 Kit / 힙(Heap)] 이중우선순위큐 (python)

풀이

import heapq

def solution(operations):
    answer = []
    minheap = []
    maxheap = []

    for ins in operations:
        a, b = ins.split(' ')
        b = int(b)

        if a == 'I':
            #heapq에 push
            heapq.heappush(minheap, b)
            heapq.heappush(maxheap, -b)

        elif a == 'D':
            #heapq에 delete
            try:
                if b < 0:
                    min_value = -(heapq.heappop(minheap))
                    maxheap.remove(min_value)

                else:
                    max_value = -(heapq.heappop(maxheap))
                    minheap.remove(max_value)
                    
            #heap이 비어있는 경우 - 명령어 무시
            except IndexError:
                continue

        else:
            break

    # 명령어 완료
    try:
        max_value = -(heapq.heappop(maxheap))
    except IndexError:
        max_value = 0
    try:
        min_value = heapq.heappop(minheap)
    except IndexError:
        min_value = 0
    
    answer.append(max_value)
    answer.append(min_value)
    return answer

내 풀이

• minheap과 maxheap을 같이 만들어 동작. minheap에서 pop을 하면 maxheap에서는 remove로 지우고, 반대일 경우도 마찬가지로 진행하여 두 heap이 동일한 자료를 가지도록 함.
• 파이썬 heapq는 최소힙으로 구현되므로 최대힙을 만들기 위해서는 -를 붙여서 만들었음 (6, 9가 들어간 경우 -를 붙이면 heapq는 -9, -6 순으로 정렬하므로 이를 이용하여 최대힙을 구현함). 최대힙에서 값을 가져올 때는 다시 -를 붙여서 원래 값이 나오도록 함.
• heap 안에 값이 없는 경우는 IndexError가 발생하므로 try except 문으로 예외 처리함