프로그래머스 Lv2 더 맵게

문제

링크

풀이

from heapq import heapify, heappop, heappush

def solution(scoville, K):
    answer = 0
    heapify(scoville)
    while scoville[0] < K :
        if len(scoville) < 2 :
            break
        mix = heappop(scoville) + (heappop(scoville) * 2)
        heappush(scoville, mix)
        answer += 1
    if scoville[0] < K :
        return -1
    return answer

heapq를 사용해서 문제를 풀 수 있었다.

문제에서 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 라고 했으므로, 최소 힙을 사용한다.

힙을 사용하기 위해 heapq를 import 하고, heapify를 이용해 배열을 힙으로 변환한다.

heapify(x)
: 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

스코빌 배열의 최소 값이 K보다 작다면 계속 반복하는 반복문을 사용했다.

이때 스코빌 배열의 길이가 2보다 작을 경우 반복을 멈춘다.
->새로운 스코빌 지수를 만들기 위해서 최소 두 개의 원소가 필요한데, 2보다 작을 경우 계산을 할 수 없기 때문이다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

스코빌 배열의 길이가 2 이상일 경우, 첫 번째로 작은 값과 두 번째로 작은 값을 heappop()으로 pop하여 위의 식을 이용해 새로운 값을 push(heappush)하고 횟수를 나타내는 변수인 answer에 1씩 더해준다.

반복문이 완료되면 스코빌 배열의 최소값을 확인한다.
이때 최소값이 K보다 작을 경우 모든 음식의 스코빌 지수가 K 이상 이어야 한다는 조건을 만족하지 않기 때문에 -1을 출력한다.
하지만 모든 음식의 스코빌 지수가 K 이상일 경우 answer를 출력한다.