[프로그래머스] 더 맵게

---

문제설명

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

코딩테스트 연습 - 더 맵게

사고과정

• 최소 힙 정렬을 이용하는 문제이다. 우선 최소 힙에다가 주어지는 스코빌 지수를 모두 담아서 최소 힙 안에서 스코빌 지수 기준으로 오름차순 정렬하도록 만든다.
• 그리고 최소 힙 길이가 1이 될 때까지 무한 반복문을 도는데, 이 때, 최소 힙의 가장 앞자리에 있는 값이 K보다 크거나 같으면 바로 break하면 된다. 왜냐하면 최소 힙 안에서 이미 정렬되어 있기 때문에 가장 앞자리가 K보다 크다는 것은 힙안에 있는 나머지 값들도 모두 K보다 크다는 것을 의미하기 때문!
• 만약 K보다 작으면 문제에서 주어지는 설명처럼 힙의 첫번째, 두번째 값을 pop한 뒤 계산한 다음 다시 힙에 넣어주어서 재정렬하도록 만들어준다.
• 그리고 힙 길이가 1이 되었을 때 반복문을 빠져나왔을 경우, 2가지 경우로 나뉘는데, 첫 번째 경우는 힙에 남아있는 1가지 지수값이 K보다 크거나 같을 경우, 작을 경우이다. 크거나 같을 경우에는 바로 횟수 answer를 리턴하면 되지만 작을 경우에는 만들 수 없는 경우이므로 -1을 출력하도록 하면 된다.

풀이

import heapq

def solution(scoville, K):
    queue = []
    for s in scoville:
        heapq.heappush(queue, s)
    
    answer = 0
    while len(queue) != 1:
        if queue[0] < K:
            one = heapq.heappop(queue)
            two = heapq.heappop(queue)
            heapq.heappush(queue, one + two*2)
            answer += 1
        else:
            return answer
    if queue and queue[0] >= K:
        return answer
    else:
        return -1