[programmers/python] - 더 맵게, 힙(Heap)

문제 조건 요약

• url : https://school.programmers.co.kr/learn/courses/30/lessons/42626
• 섞는 공식:
  새로운 음식의 스코빌 지수 = 가장 맵지 않은 음식 + (두 번째로 맵지 않은 음식 × 2)
• 음식의 스코빌 지수가 K 이상이 되면 종료한다.
• 만들 수 없는 경우는 -1을 반환한다.
• heappop()은 빈 리스트에 대해 실행하면 IndexError가 발생하므로 주의가 필요하다.

---

핵심 아이디어

• 가장 작은 값을 빠르게 꺼내야 하므로 **최소 힙(min-heap)**을 사용한다.
• heapq는 리스트를 힙 구조로 정렬할 수 있는 표준 라이브러리이다.
• heapq.heapify(scoville)를 통해 입력 리스트를 최소 힙으로 변환한다.
• 루프마다 heappop()으로 가장 작은 두 값을 꺼내어 새로운 스코빌 값을 계산하고 다시 heappush() 한다.
• 루프 종료 조건은 가장 작은 값이 K 이상이 되는 순간이다.

---

최종 코드

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)  # 리스트를 힙으로 변환
    answer = 0
    while True:
        if len(scoville) < 1:
            return -1  # 더 이상 섞을 수 없는 경우
        f1 = heapq.heappop(scoville)
        if f1 >= K:
            return answer  # 모든 음식이 K 이상이면 종료
        if len(scoville) < 1:
            return -1  # 두 번째 원소가 없으면 섞을 수 없음
        f2 = heapq.heappop(scoville)
        f3 = f1 + (f2 * 2)
        heapq.heappush(scoville, f3)
        answer += 1

---

예제 실행

print(solution([1, 2, 3, 9, 10, 12], 7))  # 출력: 2

---

동작 과정

1. 가장 작은 1, 2를 꺼내서 1 + (2×2) = 5를 만든다.
   → 리스트 상태: [3, 5, 9, 10, 12]
2. 가장 작은 3, 5를 꺼내서 3 + (5×2) = 13을 만든다.
   → 리스트 상태: [9, 10, 12, 13]
3. 모든 원소가 7 이상이 되므로 종료.
   → 총 2회 섞음 → 정답: 2