[프로그래머스] 더 맵게

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

heap을 사용하기 위해 heapq 라이브러리를 이용하였다.

input으로 들어오는 scoville을 heapify하게되면, heap형태로 변환되기 때문에

첫 번째 heapq.heappop()를 통해 가장 맵지 않은 음식의 스코빌 지수, 두 번째 heapq.heappop()를 통해 두 번째로 맵지 않은 음식의 스코빌 지수를 얻을 수 있다.

 

import heapq

def solution(scoville, K):
    # len(scoville) : 1 <= n <= 1000000
    # 최대 O(nlogn)정도
    answer = 0
    
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) <= 1:
            return -1
        
        mix_scoville = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
        heapq.heappush(scoville, mix_scoville)
        
        answer += 1
        
    return answer