[heap/프로그래머스] 42626번 : 더 맵게

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42626

 

문제 이해 

- scoville 배열에서 모든 숫자가 주어진 K 이상이 될 때까지의 연산 횟수를 반환하는 문제다. 

- 연산은 (가장 작은 수) + 2 * (두 번째로 작은 수)로 진행하며, 새롭게 업데이트 한 숫자를 다시 scoville에 추가한다. 

- 가장 작은 수를 찾아야하고, len(scoville)이 최대 백 만이기 때문에 배열에서 가장 작은 수가 0 인덱스에 있고, 시간 복잡도가 O(logn)인 heap을 이용해야한다! 

- 위와 같은 방식으로 scoville을 갱신하다가 scoville의 가장 앞 숫자가 K이상이라면 나머지 숫자들도 다 K이상이므로 while문을 break 하면 된다.

- 하지만 만약 scoville에 원소 하나만 남았는데 그 숫자가 K 미만이라면 조건을 만족하지 못하므로 -1을 출력하면 된다.

 

정답 풀이

import heapq

def solution(scoville, K):
    answer = 0 # K를 만들기 위해 섞은 횟수 
    
    heapq.heapify(scoville)
    
    while len(scoville) >= 2:
        first = heapq.heappop(scoville)
        if first >= K: # 가장 작은 수마저 K이상이므로 모든 수가 K 이상임을 알 수 있음
            break

        result = first + 2 * heapq.heappop(scoville)
        answer += 1
        heapq.heappush(scoville, result)
        
    if scoville[0] < K :
        return -1
    else:
        return answer