[코딩테스트] 힙(Heap) - 더 맵게

---

문제

 

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

프로그래머스

 

모든 음식이 어떤 K값 이상의 스코빌 지수를 가질 때까지 가장 낮은 스코빌 지수를 가진 음식 두개를 섞어 새로운 음식을 만드는 문제

 

파이썬의 힙은 최소 힙이므로 이를 이용하면 된다.

 

 

---

전략

 

01. 힙

 scoville 리스트를 힙 구조로 만든 뒤 최소값을 두개 빼내서 연산하고 다시 push하는 방식으로 하면 될 것 같다.

 

 

 

---

풀이

 

import heapq

def solution(scoville, K):
    count = 0
    
    heapq.heapify(scoville)
    
    if scoville[0] >= K:
        return 0
    
    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        
        comp1 = heapq.heappop(scoville)
        comp2 = heapq.heappop(scoville)

        new_comp = (comp1 + comp2 * 2)
        
        heapq.heappush(scoville, new_comp)
        count += 1
        
    return count

 

 최초 heapq.heapify()를 이용해 scoville 리스트를 힙 구조로 변경해준 뒤에 가장 작은 값이 K보다 작다면 while문을 돌려준다. 이 때 scoville리스트의 길이가 1이면 두 음식을 섞는 연산이 불가능하므로 -1을 리턴하도록 했다.

 

 만약 길이가 2 이상일 경우 heappop()을 이용해 최솟값 두개를 빼내 연산하고 heappush()로 다시 scoville 리스트에 넣어주었다. 이를 반복하면 된다.