힙 알고리즘

힙

: 힙은 힙의 특성을 이용하여 정렬하는 알고리즘입니다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리입니다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 합니다. 즉, 이러한 두 값의 대소 관계가 일정하면 됩니다.

힙은 '쌓아 놓음', '쌓아 놓은 더미'라는 뜻입니다.

힙에서 어떤 부모와 자식 관계를 주목할 때 '부모의 값 >= 자식의 값'인 관계가 항상 성립합니다. 따라서 힙의 가장 위쪽에 위치한 루트가 가장 큰 값이 됩니다.

더 맵게 (내가 생각한 풀이) 🧐

def solution(scoville, k):
    i = 0
    while scoville[0] < k:
        scoville = sorted(scoville)
        mix = scoville[0] + (scoville[1] * 2)
        scoville.pop(0)
        scoville.pop(0)
        scoville.insert(0, mix)
        i += 1
    return i

더 맵게 ✅

# heap을 쓴 다른 사람 풀이
# 소름 돋을 정도로 비슷한 알고리즘에 똑같은 변수명... 당신은 혹시 나의 도플갱어...?
# heappop..힙합... 힙합 보며... 혼자 껄껄댄건 조금 소름.. 알고리즘 그만 하고 싶다...ㅎ

import heapq

def solution(scoville, k):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < k:
        mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville, mix)
        answer += 1
        if len(scoville) == 1 and scoville[0] < k:
            return -1
            # -1이 break와 다름. 더 빠른 듯.
            #break
    return answer