문제 유형자체가 heap유형으로 heap으로 푸는것이라고 알려주고 있다.
힙이란!!
최대값과 최솟값을 완전이진트리로 구현된 트리이다.
최대값과 최솟값을 빠르게 찾을때 사용된다.
힙은 Min Heap 과 Max Heap으로 구성되어있는데
Min Heap - 부모 노드의 값이 자식 노드 보다 항상 작다.
Max Heap - 부모 노드의 값이 자식 노드 보드 항상 크다.
파이썬에서 제공하는 Heap
heapq
heapq는 최소 합으로 정렬된다.
heapq.heappush(heap, key)
key값을 heap에 추가
heapq.heappop(heap)
heap에서 가장작은 원소 0번째 인덱스를 삭제하고 return 한다.
heapq.heapify(list)
list를 heap으로 변환해준다.
O(N)의 시간복잡도를 가진다.
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while len(scoville) >= 1:
if len(scoville) == 1:
if scoville[0] < K:
return -1
else:
return answer
least = heapq.heappop(scoville)
if least >= K:
print(answer)
return answer
least2 = heapq.heappop(scoville)
add = least
heapq.heappush(scoville, least + (least2 * 2))
answer += 1
return -1
문제를 이렇게 풀었다!
scoville를 heapify를 이용해서 최소힙으로 만들어준다음에 scoville의 길이가 1이상일때까지 while문을 돌렸다.
그리고 while문 내부에 scoville의 길이가 1이면 2개를 합칠 수 없기때문에 여기서 원소의 값이 K보다 작으면 -1를 return 크면 answer를 return 하였다 .
이 부분이 없으면 16번 test case가 계속 틀린다!!!
그리고 최소값이 K보다 작다면 2최소값을 공식에 따라 합해서 scoville에 추가하는것을 반복한다!!
그러면 정답!!!
최대값 최소값을 빠르게 찾고싶을때! HEAP !!