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

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

 

 

처음 문제를 접근했을 때는 아래와 같이 deque으로 접근했다.

deque으로 접근하게 되면, 매번 Sorted를 통해서 정렬을 해주어야 하기 때문에 시간 초과가 발생했다.

from collections import deque
def solution(scoville, K):
    scv = deque(sorted(scoville))
    cnt = 0 
    while min(scv) < K:
        cnt += 1
        x, y = scv.popleft(), scv.popleft()
        
        scv.append(x + y*2)
        scv = deque(sorted(scv))
        
        if len(scv) == 1:
            return -1
    
    return cnt

 

힙(Heap)을 사용하게 되면, 알아서 정렬을 해주기 때문에 시간복잡도가 많이 개선된다.

힙을 사용하면 아래와 같이 풀이할 수 있다.

 

import heapq
def solution(scoville, K):
    cnt = 0 
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        scv = heapq.heappop(scoville) + heapq.heappop(scoville) * 2
        heapq.heappush(scoville, scv)
        cnt += 1
        
        if len(scoville) == 1:
            return -1 
    
    return cnt