[고득점 Kit(힙)] 이중우선순위큐 (Python)

 

코딩테스트 연습 - 이중우선순위큐

 

풀이

 최소힙과 최대힙을 각각 만들어서 값을 넣어줬다. Insert 작업이 들어오면 각각의 힙에 값을 넣어줬고 Delete 작업이 들어오면 각각의 힙에서 값을 pop해줬다. 

 마지막에 두 힙에 값이 남아있다면 answer 배열에 최댓값과 최솟값을 찾아서 넣어줬다.

 

코드

import heapq

def solution(operations):
    answer = [0, 0]

    minHeap = [] # 최소힙
    maxHeap = [] # 최대힙

    for operation in operations:
        if operation[0] == 'I': # Insert일 경우 두 힙에 값 push
            num = int(operation[2:])
            heapq.heappush(minHeap, num)
            heapq.heappush(maxHeap, -num)
        elif len(maxHeap) == 0: # delete 작업 전에 힙에 값이 없으면 continue
            continue
        elif operation == 'D 1': # delete일 경우 두 힙에서 값 pop
            heapq.heappop(maxHeap)
            minHeap.pop()
        elif operation == 'D -1':
            heapq.heappop(minHeap)
            maxHeap.pop()
            
    # 두 힙에 값이 남아있다면 최댓값과 최솟값을 넣어준다.
    if maxHeap and minHeap:
        answer[0], answer[1] = -maxHeap[0], minHeap[0]

    return answer