[프로그래머스] 힙(Heap) - 더 맵게 (Python)

[프로그래머스] 힙(Heap) - 더 맵게

• 문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42626
• 난이도: Level 2
• 알고리즘:
  • 힙(Heap)

풀이

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    cnt = 0

    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        cnt += 1
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        heapq.heappush(scoville, first + second * 2)

    return cnt

처음에 문제를 풀었을 때 정확성 테스트는 통과하지만 효율성 테스트에서 시간초과 문제가 발생했었는데, 이는 heapq로 구현하는 것을 통해 해결할 수 있었다.

---

📌 파이썬의 heapq 모듈은 최소 힙 자료구조를 제공함

• heapq.heapify(list) : 기존의 list를 힙으로 변환 (인덱스 0번에 최솟값이 위치함)
• heapq.heappop(list) : list의 가장 작은 값 삭제 후, 그 값을 리턴
• heapq.heappush(list, number) : 힙에 원소(number) 추가

• algorithms