프로그래머스 코딩테스트 고득점 Kit_힙_더 맵게

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

파이썬의 heapq모듈을 사용하여 최소힙을 구현한다.

입력받은 scoville을 sort하여 인덱스0 위치에 최솟값이 존재하게 만들어준다.

가장 안 매운 음식을 pop하여 k와 비교한다.

k보다 작으면 두번째로 안 매운 음식을 pop하여 가장 안 매운 음식과 섞어서 추가하고, 섞는 횟수를 count한다.
이때, 가장 안 매운 음식이 마지막 음식일 경우 -1을 return 하며 종료한다.

k보다 크다면 섞은횟수를 return하며 종료한다.

구현 코드👇

#섞은 횟수 return
#heapq모듈로 최소힙 구현

import heapq

def solution(scoville, K):
    answer = 0 
    scoville.sort() #최소힙에서는 가장 작은 값이 인덱스0에 위치해야한다.
    while 1:
        first = heapq.heappop(scoville) #가장 안 매운 음식
        if first < K:
            if not scoville: #마지막 음식이 k보다 작을 경우
                return -1
            second = heapq.heappop(scoville) #두번째로 안 매운 음식
            heapq.heappush(scoville, first + second*2)
            answer += 1 #섞은 횟수 카운트
        else:
            return answer