[프로그래머스] 더 맵게

코딩테스트 연습 - 더 맵게

heapq 모듈 사용법

[파이썬] heapq 모듈 사용법

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)

[1, 3, 5, 4, 8, 7]

heapify() 함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 위에서 다룬 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스에 위치됩니다. 즉, 비어있는 리스트를 생성한 후 heappush() 함수로 원소를 하나씩 추가한 효과가 납니다. heapify() 함수의 성능은 인자로 넘기는 리스트의 원소수에 비례합니다. 즉 O(N)의 시간 복잡도를 가집니다.

내 풀이

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) <= 1:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1

    return answer