[프로그래머스] 더 맵게(python)

Programmers, 더 맵게

TL;DR

• 힙(heap)

문제 요약

1. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 갖고 있는 음식을 섞어서 스코빌 지수를 늘리려고 한다.
2. 갖고 있는 음식 중 스코빌 지수를 가장 낮은 두 개의 음식을 아래와 같은 방법으로 섞어 새로운 음식을 만든다.
    `섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째 맵지 않은 음식의 스코빌 지수 * 2)`
3. 갖고 있는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.

 

- 보유 하고 있는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 스코빌 지수가 가장 낮은 2개 음식을 뽑아 주어진 공식에 맞게 섞는 것을 반복하면 된다.

- 파이썬에서는 힙(heap)이 최소 힙(min heap)으로 구현되어 있어 가장 낮은 스코빌 지수를 추출해내는데 유용하게 활용할 수 있다.

입출력 형태

입출력 예시

풀이

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while True:
        try:
            least = heapq.heappop(scoville)
            # 최소인 값이 K보다 클 경우 나머지 값들 모두 K보다 크다는 성질을 이용
            if least >= K:
                return answer
            less = heapq.heappop(scoville)
            new = least + (less * 2)
            heapq.heappush(scoville, new)
            answer += 1
        except IndexError:
            return -1

 

주어진 리스트를 힙으로 만들어 준다. 파이썬의 `heapq` 모듈에는 `heapify`라는 메소드가 있는데 이는 파라미터로 주어지는 자료를 최소 힙 구조로 만들어 준다. 이 구문이 실행되고 나면 scoville는 최소 힙 구조를 갖게 된다.

 

그 다음은 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하면 된다.

만약 뽑은 최소 음식의 스코빌 지수가 K 이상일 경우는 다른 모든 음식들의 스코빌 지수가 K 이상이다. 왜냐하면 최소 힙이기 때문에 추출하는 값이 존재하는 값 중에 최소이기 때문이다.

따라서 코드에서도 최소로 뽑은 값이 K 이상일 경우는 정답을 반환하고 종료한다.

만약 최소로 뽑은 값이 K보다 작을 경우는 문제에서 주어진 공식에 따라서 스코빌 지수를 만들면 된다. 이 때, 이 구문을 try로 감싼 이유는 모든 음식의 스코빌 지수가 K보다 작을 경우는 힙이 비게 된다. 그래서 에러가 발생하게 된다. 이 때는, 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이므로 -1을 반환하고 종료한다.

 

최소 힙의 성질을 이용해서 문제를 해결하면 된다.