🥚문제

https://programmers.co.kr/learn/courses/30/lessons/43164

• 힙(Heap)

---

🥚입력/출력

---

🍳코드

import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없음 = 더이상 섞을 것이 없음
        if len(scoville) < 2:
            return -1
        mix = heapq.heappop(scoville) + heapq.heappop(scoville)*2
        heapq.heappush(scoville, mix)
        answer += 1
    return answer

---

🧂아이디어

힙(Heap)

• 파이썬 heapq 모듈을 사용하여 정확성, 효율성 테스트 모두 통과할 수 있었던 문제

• python의 heapq 모듈은 우선순위큐 알고리즘을 구현하고 있으며,
  힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리이다.
  (출처: https://docs.python.org/ko/3/library/heapq.html)

• 인자로 받은 배열 scoville을 힙으로 변환시키기 위해 heapq.heapify 함수를 사용하였다.

• 가장 맵지 않은 음식의 스코빌 지수가 K이상이 될 때까지 음식을 섞는 것을 반복하기 위해 최소힙인 scoville의 가장 작은 항목인 scoville[0] < K인지 검사하며 while loop를 실행한다.

• 이때, 더이상 섞을 음식이 없는데 스코빌 지수 K에 도달하지 못했다면 -1을 리턴한다.

• 문제에 나온 공식인 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)는 아래 코드로 구현했다.

  mix = heapq.heappop(scoville) + heapq.heappop(scoville)*2
  heapq.heappush(scoville, mix)

• 가장 맵지 않은 음식의 스코빌 지수가 K이상이 되면, 음식을 섞은 횟수인 answer를 리턴해주면 된다.