[프로그래머스] 더 맵게 / python 힙 자료구조 모듈 heapq

문제

풀이

from heapq import heapify, heappop, heappush
def solution(scoville, K):
    heapify(scoville)
    answer=0
    new_s=0
    while scoville[0]<K and len(scoville)>1:
        new_s=heappop(scoville)
        new_s+=heappop(scoville)*2
        heappush(scoville, new_s)
        answer+=1
    if scoville[0]<K:
        return -1
    return answer

다른사람 풀이

from heapq import heapify, heappush, heappop
def solution(scoville, K):
    heapify(scoville)
    for i in range(1000000):
        try:
            heappush(scoville, heappop(scoville)+(heappop(scoville)*2))
            if scoville[0] >= K: return i+1
        except:
            return -1

배운점 : heapq

• 모듈 import

from heapq

• Heap 특징
  • 정렬된 이진트리(binary tree) 👉 시간복잡도 O(log n)
  • 리스트를 힙으로 변환 👉 heapify(리스트) / 원본리스트가 변경됨
  • 원소 추가 👉 heappush(리스트, 원소)
  • 원소 삭제 👉 heappop(리스트) : 가장 작은 값이 삭제됨