[Python] (프로그래머스 Level 3) 이중우선순위큐

[Python] (프로그래머스 Level 3) 이중우선순위큐

내 풀이

from heapq import heapify, heappush, heappop, nlargest

def solution(operations):
    heap = []
    heapify(heap)

    for operation in operations: 
        [char, value] = operation.split(' ')
        if char == 'I':
            heappush(heap, int(value))
        else:
            if len(heap) > 0: 
                if value == '1':
                    heap = nlargest(len(heap), heap)[1:]
                    heapify(heap)
                else:
                    heappop(heap)

    if heap: 
        return [nlargest(1, heap)[0], heap[0]]
    else: 
        return [0,0]

• 테스트 케이스 3, 6 에서 계속 실패했는데,,, 알고 보니 테케가 약해서 2개밖에 실패하지 않은거였다. 사실 엄청 틀린거였음..!
• 뭐가 틀렸냐면..

heap = nlargest(len(heap), heap)[1:]
heapify(heap)

여기서 heap의 최댓값을 잘라서 list를 강제로 넣고 나서 다시 heapify하지 않았다는 것…

python 의 heapq는 기본적으로 minHeap을 만드는 것이고, 그 때의 루트 노드는 list의 0번째 인덱스가 된다. 근데 강제로 nlargest로 배열을 정렬하고 1번부터 끝까지 잘라내어 새로운 배열을 만들어 heap에 할당해준 상태라서 heap 구조가 깨진 상태인것이다.

이를 다시 힙 구조로 만들어 주기 위해 heapify를 해줘야했었다.

만약 정렬하지 않고 최댓값을 찾아서 최댓값에 해당하는 index를 pop해주는 형태로 갔으면 heapify하지 않아도 됐을 것 같다.

배운 점, 느낀 점

• heapq 에는 nlargest, nsmallest라는 함수가 있다..!