[programmers] Heap - 더 맵게

문제링크

코딩테스트 연습 - 더 맵게

문제 해설

음식의 스코빌 지수를 담은 배열 scoville이 주어지면, 모든 음식을 섞어 K이상의 스코빌 지수를 만드려고 한다. 이때, 스코빌 지수는

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

IN
음식의 스코빌 지수를 담은 배열 scoville
모든 음식을 섞어 만들고자 하는 스코빌 지수 K

OUT
섞어야 하는 최소 횟수

제한사항

• 2 <= len(scoville) <=1,000,000
• 0<= K <= 1,000,000,000
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• K 이상으로 만들 수 없는 경우에 -1을 return

접근

최소번 섞어서 모든 음식의 스코빌 지수를 k이상으로 만들려면 스코빌 지수가 k이하인 음식들을 섞어야한다
-> mim heap을 이용해 스코빌지수가 낮은 음식들부터 섞는다

프로그래머스 - 더맵게

---

import heapq

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