알고리즘 고득점 Kit - 힙 큐 - 더 맵게

 

문제 풀이

1. 힙큐 사용을 위해 import heapq 입력

2. scoville에 heapq를 사용하기 위해 heapify를 적용시켜 힙큐로 만듦

3. scoville의 길이가 2 이상인 경우 계속 반복하는 while문 작성
   (길이가 1이 되면 끝까지 섞은 경우이므로 K보다 높은지 낮은지 비교해서 answer / -1 결정)

4. 만약 scoville의 0번째(가장 작은 수)가 K보다 크면 answer를 반환하고 종료

5. 아니라면 scoville에서 heappop으로 가장 작은 수 두개를 빼와서 first + second * 2를 하고 다시 heappush로 집어넣음

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) >= 2:
        if scoville[0] >= K:
            return answer
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        assem = first + second * 2
        heapq.heappush(scoville, assem)
        answer += 1
    
    return answer if scoville[0] >= K else -1

 

** 이 코드는 heapify를 모르던 상태에서 scoville을 힙큐로 만들었던 방법, 두 방식의 시간 차이가 거의 없었으나 실제 시간 복잡도는 heapify = n 이고 heappush는 nlogn 이기 때문에 가능하다면 heapify를 사용하는게 효율적이다 **

import heapq
def solution(scovilled, K):
    answer = 0
    scoville = []
    for i in scovilled:
        heapq.heappush(scoville, i)
    
    while len(scoville) >= 2:
        if scoville[0] >= K:
            return answer
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        assem = first + second * 2
        heapq.heappush(scoville, assem)
        answer += 1
    
    return answer if scoville[0] >= K else -1