[Python | 파이썬] 더 맵게 (프로그래머스 HEAP)

[Python | 파이썬] 더 맵게 (프로그래머스 HEAP)

 

 

최소힙을 이용할 수 있는 heapq를 이용해서 스코빌지수가 작은 원소부터 맨 앞에 오도록 heap에 push해준다.

가장 안 매운 두 음식을 섞어준 뒤에 다시 heap에 추가해준다. 섞은 횟수를 증가시키고, 만약 모든 음식의 스코빌지수가 k이상인지 확인하는 함수의 return 값이 True라면 반복문을 종료하고 answer를 return한다. 

만약 heap에 원소가 한 개 남았다면 모든 음식을 섞어도 스코빌지수를 k이상으로 만들지 못한 것이므로 -1을 return한다.

 

import heapq
def check(h, k):
    for i in h:
        if i < k:
            return False
    return True

def solution(scoville, k):
    answer = 0
    h = []
    for i in scoville:
        heapq.heappush(h, i)
    
    while True:
        if len(h) == 1: return -1
        first = heapq.heappop(h)
        second = heapq.heappop(h)
        heapq.heappush(h, first + second*2)
        answer += 1
        if check(h, k):
            return answer

 

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

프로그래머스