더 맵게

설명

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

import heapq
def solution(scoville, K):
    count = 0
    # scoville.sort()
    # while scoville[0]<K:
    #     if len(scoville) < 2:
    #         return -1
    #     new = scoville.pop(0) + (scoville.pop(0)*2)
    #     scoville.append(new)
    #     scoville.sort()
    #     count += 1
    # 정확성 테스트 모두 통과
    # 효율성테스트 걸림 - list 크기가 백만이라 매 loop마다 sort하는게 빡센가보다
    # 왜 heap인가 했더니 힙은 원소 pop, push마다 자동으로 정렬
    # 파이썬에서 따로 힙이 있나 구글링 결과 heapq 발견
    heapq.heapify(scoville)
    while scoville[0]<K:
        if len(scoville) < 2:
            return -1
        new = heapq.heappop(scoville) + (heapq.heappop(scoville)*2)
        heapq.heappush(scoville, new)
        count += 1
    
    answer = count
    return answer

• 처음엔 힙으로 안 짜고 그냥 짰더니 정확성은 통과하는데 효율성에서 실패했다.
• 문제는 매 loop마다 정렬을 하니 시간이 오래 걸려서인 듯 하다.
• 그래서 구글에 heap을 찾아봤더니 python에서 heapq를 알아냈다.
• 별 다를건 없고 기존 리스트를 heap으로 수정하여 sort만 빼줬더니 가뿐하게 통과했다.