방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제는 heapq를 이용하면 쉽게 해결할 수 있는 문제였습니다. 매번 정렬을 한다면 효율성의 문제가 생길 수 있으므로 최소힙을 이용해 O(logN)으로 가장 작은 값을 꺼내면 됩니다. 이 때 2개씩 꺼내어 더 맵게 하는 과정을 거치는데 q의 길이가 1이라면 두번을 꺼낼 수 없으므로 예외처리를 따로 해주시면 됩니다.

소스코드

import heapq

def solution(scoville, K):
    answer = 0
    q = []
    for i in range(len(scoville)):
        heapq.heappush(q, scoville[i])
    while True: 
        if len(q) >= 2:
            num1 = heapq.heappop(q)
            num2 = heapq.heappop(q)
        elif len(q) == 1:
            num1 = heapq.heappop(q)
            if num1 < K:
                answer = -1
                break
        if num1 >= K:
            break
        answer += 1
        heapq.heappush(q, (num1 + num2 * 2))
    
    return answer