[Programmers] 더 맵게 - 42626

첫 Heap 문제 ! 우선순위큐 ! 너무 유용하고 빠르고 편하고 좋다 ^^..

 

Question

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

Point

 

• heapq를 이용하여 작은 값 두 개 m1, m2 뽑고 가장 작은 m1이 K보다 크다면 return.
• 마지막에 모든 음식이 K 이상인지 확인하고 아니라면 -1 return.

 

Code

 

import heapq
def solution(scov, K):
    cnt = 0
    heapq.heapify(scov)
    while len(scov) > 1:
        m1 = heapq.heappop(scov)
        m2 = heapq.heappop(scov)
        if (m1 >= K) : return cnt
        new = m1 + m2*2
        heapq.heappush(scov, new)
        cnt += 1
        
    return cnt if scov[0] >= K else -1

 

now me

On my github