[프로그래머스/Python] 힙 - 더 맵게

👩🏻‍🏫 풀이

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    # 최소값이 K보다 작다면 계속 반복하라
    while scoville[0] <= K:
        mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville,mix)
        answer += 1
        # 리스트 안의 값이 1개가 됐는데도 K보다 작다면 -1
        if len(scoville) == 1 and scoville[0] < K:
            return -1
    return answer

✏️ Python 문법

heapq모듈

• 가장 작은 값이 최상단(인덱스 0)
  • 힙에서 인덱스 0이 최솟값이라고 해서, 인덱스 1에 두 번째, 인덱스 2에 세 번째로 작은 원소가 있는 것이 아니다
  • heappop() 함수를 호출하여 원소를 삭제할 때마다 이진 트리의 재배치를 통해 매번 새로운 최소값을 인덱스 0에 위치시키기 때문
  • 따라서 두번째로 작은 원소를 얻으려면 바로 heap[1]으로 접근하면 안되고, 반드시 heappop()을 통해 가장 작은 원소를 삭제 후에 heap[0]를 통해 새로운 최소값에 접근해야 합니다.

• 파이썬 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 $O(NlogN)$에 오름차순 정렬 완료

• 파이썬에서는 최대 힙을 제공하지 않는다.

  • heapq라이브러리를 이용하여 최대힙을 구현해야 할 때는 원소의 부호를 임시로 변경하는 방식을 사용
  • 힙에 원소를 삽입하기 전에 잠시 부호를 반대로 바꾸었다가, 힙에서 원소를 꺼낸 뒤에 다시 원소의 부호를 바꾸면 된다.

import heapq
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)           # [1, 3, 7, 4]

# pop
heapq.heappop(heap)
print(heap)           # [3, 4, 7]

# 최소값 삭제하지 않고 얻기
print(heap[0])        # 3

# 기존 리스트를 힙으로 변환
list = [4,1,7,3,8,5]
heapq.heapify(list)
print(list)           # [1, 3, 5, 4, 8, 7]