[프로그래머스] 더 맵게(힙) - Lv2

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

처음에 어차피 힙은 배열로 구현하니까 배열로 하면 풀 수 있을꺼야 라는 어리석은 생각을했다. ㅠ 찾아보니 heapq라이브러리를 통해 구현을 해야 효율성 테스트를 통과할 수 있었다.

 

풀이

import heapq

def solution(scoville, K):
    answer = 0

    # 힙으로 변환
    heapq.heapify(scoville)

    while scoville[0] < K:
        scoville1 = heapq.heappop(scoville)
        scoville2 = heapq.heappop(scoville)

        heapq.heappush(scoville, scoville1 + scoville2 * 2)
        answer += 1
        if len(scoville) < 2 and scoville[0] < K:
            return -1

    return answer

 

 

해설

heapq 라이브러리를 사용하면 그 이후에는 문제에서 하라는대로 구현만 하면된다. heapq 사용시 주의해야할 점은 heapq로 변환한 배열의 맨앞요소는 제일 작은 수 이지만 두번째 요소는 두번째로 작은 수가 아니라는 점이다. 따라서 직접 하지말고 첫번째, 두번째 최솟값을 뺄때 heappop()을 이용해서 빼준다. 

문제에서 제시한 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우는 남아있는 요소가 2개 미만이고 scoville[]의 최소인 요소가 K를 안넘었을때 return -1을 해야한다