[프로그래머스] 더 맵게 (by Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

 

풀이

import heapq


def solution(scoville, K):
    count = 0
    scoville.sort()
    while len(scoville) != 1:
        temp = heapq.heappop(scoville) + 2 * heapq.heappop(scoville)
        heapq.heappush(scoville, temp)
        count += 1
        if scoville[0] >= K:
            return count
    return -1

 

    스코빌 지수를 담은 array가 정렬되어있다고 가정했을 때, 가장 작은 2개로 제시된 알고리즘을 계속 진행해주면 된다. 다만, 정렬되어있는 상태를 유지하는 것이 어려울 수 있다. 가장 작은 2개로 알고리즘을 수행하고 새로 생성된 음식의 스코빌 지수를 array에 넣어줄 때 그 순서를 알 필요가 있기 때문이다. 이를 처리하기 쉽게 하기 위해 heap을 차용하는 것이 핵심 아이디어.