[프로그래머스] 더 맵게 _ 파이썬

• heapq 모듈을 사용한 풀이

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        if len(scoville) > 1:
            answer += 1
            least = heapq.heappop(scoville)            
            next = heapq.heappop(scoville)
            heapq.heappush(scoville, least + next*2)
        else:
            answer = -1
            break
            
    return answer

처음에는 그냥 sort를 써서 풀까 했는데 매번 sort하면 시간복잡도에서 차이가 클 것 같아 수정.

heapq를 사용하는 이유

• heapq는 최솟값(또는 최댓값)을 계속 뽑아내야 할 때 사용하면 좋다.
• 처음 정렬할 때는 시간 복잡도가 같지만
  새로운 값들이 계속 추가된다면 최솟값을 찾기 위해 원소를 매번 전체 검색하거나 정렬해야 함. -> 느림.
• 이진'검색'트리는 이진'검색'에 최적화, 힙은 연속적으로 '최솟값' 찾는데 최적화.
  -> 이진 검색 트리는 좌우로 크고 작음을 나누지만, 힙은 위아래로 나누기 때문
• heapq는 list와 tree 장점 모두 이용

1. tree 구조 사용
   -> 요소 삽입 및 루트 노드(최솟값/최댓값) 제거 시 발생하는 요소의 검색 및 스왑의 회수가 일반적 list 사용할 때보다 훨씬 작음
2. list 사용
   -> class보다 빠름

• index : x의 왼쪽 자식은 2x+1, 오른쪽 자식은 2x+2