Q1 더맵게 feat.Heap

문제 읽어보기

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

알고리즘

• 힙 (Heap)
  • 완전 이진 트리를 사용하는 알고리즘이다.
    • 완전 이진 트리 : 트리에 원소를 삽입할 때, 한 층에 왼쪽부터 차례대로 삽입되는 트리
  • 최솟값 혹은 최대값의 원소를 구할 때, 빠르게 원소를 얻을 수 있다.
  • 연산 (Python)
    • 힙 구성 : heapq.heapify(L) -> O(N log N)
    • 삽입 : heapq.heappush(L, x) -> O(log N)
    • 삭제 : heapq.heappop(L) -> O(log N)
  • 힙의 응용
    • 정렬 (Heapsort) : 모든 원소를 삽입하고, 다시 힙이 빌때까지 삭제하면 정렬이 된다.
    • 우선 순위 큐(Priority queue) : 원소들이 우선순위를 따라 빠져나오는 큐

코드

내코드

import heapq

def solution(scoville, K):
    answer = 0
    heap = []
    
    for item in scoville:
        heapq.heappush(heap, item)

    while(len(heap) > 1 and heap[0] < K):
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        heapq.heappush(heap, first + second*2)
        answer += 1

    if(heap[0] < K):
        answer = -1
    return answer

수정 코드

import heapq

def solution(scoville, K):
	answer = 0
    
    heapq.heapify(scoville) # O(N)
    
    #무한루프지만, 리스트에 원소가 1개 남았을 때 탈출하기 때문에 O(N-1)이라 볼 수 있다.
    while True:
    	min1 = heapq.heappop(scoville) # O(log N)
        if(min1 > K):
        	break
        elif(not scoville):
        	answer = -1
            break
        
        min2 = heapq.heappop(scoville) # O(log N)

        heapq.heappush(scoville, min1 + min2 * 2) # O(log N)
        answer += 1
        
   return answer