[프로그래머스] Heap__더 맵게

[프로그래머스] > 코딩테스트 연습 > 힙(Heap) > 더 맵게

python 힙(Heap)

1. 문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

1. 제한사항

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

2. 입출력 예

scoville	K	return
[1,2,3,9,10,12]	7	2

2. 풀이

import heapq //heapq 라이브러리 불러오기

def solution(scoville, K):
    answer = 0
    s_lst = scoville
    heapq.heapify(s_lst) // 리스트를 힙(기본값 최소힙)으로 변환하기(정렬)
    node_size = len(s_lst) // 힙 크기(예제에서 6)
    
    while (node_size > 1 and s_lst[0] < K):
        min_n = heapq.heappop(s_lst) // 최소힙이므로 제일 작은 값 꺼내기
        min_m = heapq.heappop(s_lst) // 그 다음 작은 값 꺼내기
        heapq.heappush(s_lst, min_n + (min_m * 2)) // 섞은 음식 힙으로 추가(최소힙조건 만족)
        answer += 1 // 섞은 횟수
        node_size -= 1 // 힙 크기(섞이므로 줄어듦)
    
    if (s_lst[0] < K): // 모든 음식을 섞었음에도 조건을 만족하지 못했을 경우
        return -1
    
    return answer