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

문제

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

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

 

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

 

 

 

 

내 생각

힙을 사용해야만 하는 문제이다. (모르면 통과할 수 없을 듯)

배열에서 가장 작은 수 2개를 더하면서 배열의 모든 수가 K보다 크도록 해야 한다.

heapq을 이용해서 풀면 정렬이 되기 때문에 시간복잡도가 좋아 쉽게 해결할 수 있다!

자세한 풀이는 주석으로 설명했다 !

 

 

 

 

내 코드

import heapq

def solution(scoville, K):
    heapq.heapify(scoville) # scoville을 힙으로 변환
    cnt = 0
    # 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복
    while scoville[0] < K:
        if len(scoville) < 2:     # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우(음식이 2개 미만)
            return -1  
        # 가장 맵지 않은 두 음식을 꺼내서 섞음
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        mixed = first + (second * 2)
        # 섞은 음식의 스코빌 지수를 힙에 추가(작은 값이 맨 앞에 위치한다)
        heapq.heappush(scoville, mixed)
        cnt += 1
    return cnt

 

 

 

 

** heapq

: 최소 값이나 최대 값을 찾기 위한 트리 형식의 자료 구조(sort 필요없이 정렬된다.)

import heapq
heapq.heapify(list) # 기존의 리스트를 오름차순 heapQ로 변환
heapq.heappop(list) # list의 가장 작은 값을 return, 삭제
heapq.heappush(list, value) # list에 value를 삽입(자동 정렬)