[Python] 더 맵게

✏️ 문제

 

문제 파악

scoville 길이가 최대 1,000,000이기 때문에 배열을 반복문을 통해 돌면 당연히 시간복잡도에서 걸린다. 

 

이때 이 문제는 힙을 사용하면 좋은데 이유는 최소값이나 최대값을 효율적으로 빠르게 추출해야 하고 힙 속성 덕분에 힙에 넣으면 자동으로 정렬이 되기 때문이다.

배열은 특정 값을 찾을 때 최악의 경우 O(n)이라는 시간이 소요되고, 계속해서 정렬을 해줘야하는 반면

힙은 최소값이나 최대값을 찾을 때 O(1)이라는 시간이 소요된다. 

 

그래서 이러한 힙을 활용해서 문제를 풀면 쉽게 풀 수 있다. 

 

 

코드

import heapq

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