[프로그래머스 lv2] 더 맵게 - 힙(heap) - 파이썬(Python)

문제

프로그래머스

시행착오 (list 이용)

83.9점 - 정확성 테스트 통과, 효율성 테스트 실패(시간초과)

def solution(scoville, K):
    cnt = 0
    while min(scoville) < K:
        if len(scoville) == 1:
            return -1
        scoville.sort()
        scoville.append(scoville[0]+scoville[1]*2)
        scoville = scoville[2:]
        cnt += 1
    return cnt

정답 (heapq 이용)

list를 이용할 때와 같은 풀이방식이지만, heapq를 이용하면 더 효율적이다.

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

설명

import heapq : 부모 노드의 키 값 >= 자식 노드의 키 값 인 최소힙(min heap) 내장모듈

heapq.heapify(scoville) : 주어진 scoville(리스트)을 힙 자료구조로 변환

heapq.heappush(scoville, item) : scoville(힙)에 item을 추가

heapq.heappop(scoville) :  scoville(힙)에서 가장 작은 원소를 제거 + 반환

scoville[0] : scoville(힙)에서 가장 작은 원소를 제거하지 않고 반환

결과