[프로그래머스] 더 맵게

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

코딩테스트 연습 - 더 맵게

heap을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약해보면, 

 

매번 매운음식의 array 안에서 가장 덜매운 음식과, 두번째로 덜매운 음식을 꺼내서 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

다음과 같이 섞은후 다시 넣어주는 과정을 반복해 모든 음식이 일정량 보다 매워질 때 까지 걸리는 섞는 횟수를 구하는 문제입니다. 

 

<Solution>

heapq 모듈을 이용하여 내부적으로 자동정렬이 되도록 해서 매번 새로운 음식을 만들어 넣어주는 형태로 구현하였습니다. 

만들수 없는 경우에 -1을 return해야 하는 경우만 신경써서 코딩을 해주면 됩니다.

실제 구현은 아래와 같습니다.

import heapq

def solution(scoville, K):
    heap = []
    for _ in range(len(scoville)):
        heapq.heappush(heap,scoville.pop())
    
    answer = 0
    while(heap):
        e = heapq.heappop(heap)
        if e >= K:
            break
        else:
            if len(heap) == 0:
                return -1
            answer+=1
            heapq.heappush(heap,e+(2*heapq.heappop(heap)))

    return answer