[Python] 프로그래머스 - Level2 - 더 맵게

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

힙(Heap)

from heapq import heappush, heappop, heapify

def solution(scoville, K):
    heapify(scoville) # list를 Heap으로 변환
    count = 0
    for i in range(len(scoville)):
        if scoville[0] <= K and len(scoville) != 1:
            heappush(scoville, heappop(scoville) + heappop(scoville) * 2)
            count += 1
        elif  scoville[0] >= K:
            return count
        else:
            return -1

레벨 넘어가는데 너무 오래 걸렸다..
시간 날 때마다 레벨2 문제 하나씩 건드려봤는데 하나도 안 풀려서 자괴감 들었음
이것도 계속 안 풀리던데 저 heapq를 꼭 사용해야 풀리는 문제인 거 같음..
레벨2부터는 진짜 자료구조 개념 정리가 필요한 것 같다.

Heap을 아주 간단히 살펴보자.

• 왼쪽 자식의 인덱스: (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스: (부모의 인덱스) * 2 + 1
• 부모의 인덱스: (자식의 인덱스) / 2

heapq는 최소 힙 (Min Heap) 기반이다.

Max Heap은 최댓값을, Min Heap은 최솟값을 빨리 찾을 때 사용!

Min Heap

• 최상위 루트 노드에 최솟값이 들어옴
• 부모 노드의 값이 자식 노드의 값보다 작음

그림으로 이해해보자 (트리에 관한 설명은 생략)

http://pages.di.unipi.it/marino/pythonads/Trees/BinaryHeapImplementation.html

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  

    return answer

내 코드랑 비교해보면 두 개를 한 번에 뽑느냐 하나씩 뽑느냐에서 차이가 있다.
하나씩 뽑으니까 코드가 조금 길어져도, -1을 return하는 부분이 좀 더 깔끔하게 나오는 것 같음

1. Level2 부터는 계속 생각이 안나면 필요한 라이브러리 정도는 참고하고 다시 풀어보자
2. 라이브러리를 사용하면 그에 대한 개념도 숙지하자