[algorithm] 프로그래머스 - 더 맵게 (파이썬)

📚 문제

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입력 예시

[1, 2, 3, 9, 10, 12], 7

출력 예시

2

🧑🏻‍💻 풀이 과정

• heapq를 사용해야한다. (이진 트리(binary tree) 기반의 최소 힙 자료구조)
• heapq에서 가장 작은 값이 K와 같거나, 클 동안 반복하자.
• 입력받은 scoville을 내림차순 정렬 후, heapify()를 이용하여 리스트를 힙으로 변환하자.
• heappop()은 힙에서 가장 작은 원소를 삭제 후, 그 값을 리턴해준다. heappop()으로 가장 작은 값과 두 번째로 작은 값을 가져오자.
• 가장 작은 값과 두 번째로 작은 값의 연산 결과를 heapq에 저장하자.

import heapq as hq


def solution(scoville, K):
    # 내림차순 정렬 후, heapq!
    scoville.sort()
    hq.heapify(scoville)

    answer = 0
    # 스코빌의 최저치가 k 이하일 동안 반복..
    while scoville[0] <= K:

        # [1, 2], 7 일 경우도 있으니까..
        if len(scoville) == 1: return -1

        answer += 1

        # 스코빌에서 첫 번째로 작은 값 + 두 번째로 작은 값 추출 후, pop
        first = hq.heappop(scoville)
        second = hq.heappop(scoville)

        # 계산한 결과 힙에 저장
        hq.heappush(scoville, first + (second * 2))

    return answer


# 테스트를 위한 코드입니다.
print(solution([1, 2, 3, 9, 10, 12], 7))