(Python) - 프로그래머스 : 더 맵게

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

코딩테스트 연습 - 더 맵게

 

• 해설 : 

맵기 정도인 스코빌 지수들이 나열될 배열이 주어질 때 가장 낮은 두 스코빌지수를 섞어 새로운 스코빌 지수를 만든다. 이 때, 모든 스코빌 지수가 K 이상이 될 때까지 최소 횟수로 섞은 경우를 리턴하면 된다.

 

 

 

 

• 풀이 :

heap을 사용하여 해결하면 된다. 처음 시도때는 두 min 값을 찾을 때, 매 번 새로 sort하여 구현하려 하였으나 시간초과에 걸려서 새로운 방법을 찾아보았다. python에서는 기본값이 min-heap이므로 heapq를 import하여 매번 새로 삽입하고 heap의 0번째 요소가 K 이상일 때 cnt를 리턴하면 된다. 

 

 

 

 

import heapq
 
def solution(scoville, K):
    answer = 0
    heap = []
    for i in scoville:
        heapq.heappush(heap,i)
    while heap[0] < K and len(heap) > 1:
        heapq.heappush(heap,(heapq.heappop(heap)+heapq.heappop(heap)*2))
        answer += 1
    if len(heap) == 1:
        if heap[0] < K:
            return -1
        
    return answer