프로그래머스 : 더 맵게

 

 

문제 링크

 

import heapq

def solution(scoville, K):
    answer = 0
    
    heapq.heapify(scoville)
    while scoville[0]<K:
        x = heapq.heappop(scoville)
        y = heapq.heappop(scoville)
        new = x + y*2

        heapq.heappush(scoville, new)
        answer+=1
        
        if len(scoville)==1 and scoville[0]<K:
            answer=-1
            break
    
    return answer

 

• 문제를 풀며 느낀 점
  • 빈 리스트가 아니라 기존에 존재하던 리스트를 heap으로 사용하고 싶으면 heapq.heapify()함수를 꼭 적용해줘야 한다.
  • min heap에서의 최솟값은 루트 노드인 heapp[0]이므로 min() 함수를 적용하지 않아도 된다. 처음에 min() 함수 썼다가 효율성 테스트에서 아웃됐다...
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -> 스코빌 지수 리스트가 하나밖에 남지 않아 더 이상 새로운 스코빌 지수로 조합할 수 없음에도 K보다 작은 경우였다.