99클럽 코테 스터디 5일차 TIL + 힙(Heap): 더 맵게

문제

링크텍스트

풀이

• heap을 안 쓰면 시간초과 발생
• return 에 지난 문제에서 배운 tip 활용
• heap은 완전 이진 트리의 일종으로 최대값, 최솟값을 쉽게 추출할 수 있다고 합니다. (ref.
  링크텍스트, 삽입과 삭제에 O(logn))

결과

def f_t(id_t):
    if id_t == 0:
        scoville, K, r = [1, 2, 3, 9, 10, 12],	7,	2
    return scoville, K, r

import heapq

def solution(scoville, K):
    n = len(scoville)
    heap = []
    for i in range(n):
        heapq.heappush(heap, scoville[i])
    min_K = heap[0]

    cnt = 0
    while min_K < K:
        if len(heap) < 2:
            return -1
        i1 = heapq.heappop(heap)
        i2 = heapq.heappop(heap)
        i3 = i1 + (i2*2)
        heapq.heappush(heap,i3)
        min_K = heap[0]
        cnt += 1
    return cnt if min_K >= K else -1

for i in range(1):
    scoville, K, r = f_t(i)
    a = solution(scoville, K)
    print([a,r])