[PROGRAMMERS]-더 맵게 (힙)

📃 더 맵게

알게 된 것

• Python의 heapq 모듈

import heapq

# 최소 힙 생성, push
heap_list = []
heapq.heappush(heap_list, 4)
heapq.heappush(heap_list, 1)
heapq.heappush(heap_list, 7)

# pop
heapq.heappop(heap_list)

# pop하지 않고 최솟값 얻기
print(heap_list[0])

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

• 힙에서 인덱스 0이 최솟값이라고 해서, 인덱스 1에 두 번째, 인덱스 2에 세 번째로 작은 원소가 있는 것이 아니다.
  두 번째로 작은 원소를 얻으려면 heappop()을 통해 최솟값을 삭제한 후 heap[0]로 접근하는 방법을 사용하거나, 인덱스 1을 인덱스 2와 비교하는 방법을 사용해야 한다.

코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K : 
        if len(scoville) == 1  :
            return -1
        first_min=heapq.heappop(scoville)
        second_min=heapq.heappop(scoville)

        heapq.heappush(scoville,first_min + second_min*2)
        first_min = scoville[0]

        answer += 1
        
    print(answer)

    return answer