학습 주제
힙을 이용한 코드 구현
파이썬 내장 함수 heapq 이용

학습 내용

문제

아이디어

• 제한사항: 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1 return
• 가장 작은 수 + 그 다음 작은 수의 연산이 반복됨.
• 중간의 값을 찾거나, 삭제할 필요가 없음.
• 반복문을 통한 연산의 반복
• 시간 복잡도는 전체 n회를 순회하고, 내부에 heap 연산으로 logn ->O(NlogN)

알고리즘

• while True 순회
• min1 = 최소힙.pop
• 분기점 2개
• min1 >= K -> break
• min1을 pop 후에 scovile == 0 break
• min2 = heap.pop
• new_scovile = min1 + 2 * min2
• heappush(scovile, new_scovile) min heap 유지
• answer += 1
• return answer

내 풀이

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while True:
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) == 0:
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_scoville = min1 + 2 * min2
        heapq.heappush(scoville, new_scoville)
        answer += 1
    return answer

어려운 점

강의를 듣고 난 후로 크게 어려운 점은 없었다. 이후 다시 풀 때 내장 힙을 편하게 쓸 수 있을 정도의 메서드 기능, 그리고 이번엔 다루지 않았지만 최대 힙도 풀어보면 좋겠다.