2022.06.06 [프로그래머스] (python 파이썬) 더 맵게

 

 

 

 

 

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

코딩테스트 연습 - 더 맵게

 

---

풀이

이 문제는 scoville배열에서 가장 작은 값이 K보다 작으면 (가장 작은값+(그 다음 작은값*2))을 더해주면서 모든 음식이 K이상일때의 더한 횟수를 구해야한다.

그래서 매 상황마다 배열을 정렬하게 되면 시간복잡도가 매우 커지기 때문에 heap을 이용해 0번째 인덱스의 값을 K와 비교하고 작으면 heap배열에서 두개를 떠내 (가장 작은값+(그 다음 작은값*2))값을 넣어주는 과정을 반복했다.

여기서 만약 scoville배열의 길이가 1보다 작거나 같으면 더이상 음식을 합칠 수 없기 때문에 while문을 빠져나왔다.

그리고 scoville[0]을 K와 비교해 K보다 작으면 해당 음식으로 K이상의 맵기를 만들 수 없기 때문에 answer에 -1을 저장했다.

 

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