프로그래머스[Python] - 더 맵게 풀이

풀이

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)의 식을 보며 O(NlogN)의 시간 복잡도를 가지는 heap 구조를 가지고 접근을 하였다.

import heapq
def solution(scoville, K):
    count = 0	## 총 섞은 횟수를 저장하는 변수
    heapq.heapify(scoville)	## Heap 구조로 만들기

    while len(scoville) >= 2: ## Heap 안에 한 개만 있으면 오류 나니까
        if scoville[0] >= K:	## Heap에서 가장 작은 값이 K보다 크다면 While문 종료
            break		
        
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        new = first + second * 2
        heapq.heappush(scoville, new)
        count += 1		## 섞은 횟수 추가
    
    last = heapq.heappop(scoville) ## Heap 안에 값 popup시키기 
    if last < K: ## K보다 작을 때
        return -1
    else:
        return count