[프로그래머스] 문제풀이 - 더 맵게

사용한 풀이법 : heap

---

풀이 과정

최소값과 그 다음값을 탐색, 계산 후 다시 삽입 => 해당 연산이 조건을 충족할 때 까지 반복되어야 함. 
이를 위한 자료구조가 바로 최소힙!

1. heapify 메서드를 통해 scoville 리스트를 최소힙으로 초기화
2. 항상 최소값을 뽑아내는 heappop 연산을 통해 min1, min2를 설정
    이때, min1이 k이상이거나, 더 이상 뽑아낼 원소가 없을때는 반복문 종료
3. 삽입할 원소를 계산 후, 힙에 push
4. 연산이 완료 될 때마다 +1한 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 = min1 + min2*2
        heapq.heappush(scoville, new)
        answer += 1
    return answer