[고득점 Kit(힙)] 더 맵게 (Python)

 

코딩테스트 연습 - 더 맵게

 

풀이

 최소힙을 사용하여 해결할 수 있다. 최소힙에서 두 개를 pop해서 문제에서 주어진 식대로 계산하여 다시 힙에 넣어주면 된다. 이때 첫번째로 꺼낸 값이 K이상이면 나머지 값도 전부 K이상이라는 의미이므로 진행을 중단한다. 

 

 마지막에 한 번 더 heap에서 값을 꺼내어 해당 값이 K 이상인가를 체크했는데 이는 마지막으로 heap에 두 개의 값이 남아있고 해당 값을 주어진 식대로 계산하여 K이상을 만족하게 됐을 때를 체크 하기 위해 추가하였다. 

 

코드

import heapq


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

    while len(scoville) >= 2:
        first = heapq.heappop(scoville)
        if first >= K:
            break 

        second = heapq.heappop(scoville)

        heapq.heappush(scoville, first + second*2)
        answer += 1

    minScoville = heapq.heappop(scoville)

    if minScoville >= K:
        return answer 
    else:
        return -1