프로그래머스 - 더 맵게.py

< 정답 코드 >

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        heapq.heappush(scoville,first+second*2)
        answer += 1
    return answer

 

< 초반에 틀렸던 이유 >

1. heapify 사용 오류 

heapify 는 heapq.heapify(list_name) 방법으로 사용하고, 리스트 자체가 힙이 된다.

2. while문 조건 & 만들어지지 않는 조건 잘못 사용

어차피 최소힙이므로 이 중 최소값만(즉 [0]값) K보다 큰 지 작은 지 while loop 검사하면 된다. 

또한 반복할 수록 두 가지 음식이 하나로 합쳐지기 때문에, 초기 조건이 음식은 2가지 이상인 것이다. 반복할 수록 음식의 수는 줄어들고, 만약 1개까지 줄어들었다면 더 이상 음식을 합칠 수 없고, 이때도 목표 스코빌 지수를 넘지 못 했다면 return -1 해야한다. 

 

음식이 갈 수록 줄어든다는 것을 캐치하지 못 해서 모두 0인 경우에만 만들 수 없는 경우라고 생각했다. 이것 때문에 통과할 수 없는 테스트 케이스가 있었다.

 

heap은 최소힙(또는 최대힙처럼)으로 쓸 수 있으므로, 이런 숫자 최소최대 비교가 필요한 리스트 연산에서 시간초과 없이 사용할 수 있다.

이 문제는 그냥 리스트로 pop, append하면 시간초과가 발생하는 문제이다 ~!! 힙은 이런 경우에 사용하도록 하자 ~!

 

< 힙 함수 >

heapq.heappush()

heapq.heappop()

heapq.heapify()

heapq.nlargest()

heapq.nsmallest()