[ PS / Python ] 42626. 더 맵게

풀이.

가장 첫 시도는 일반적인 리스트로 문제를 해결해보려고 했으나, 역시나 시간 초과가 발생했다.

그래서 힙큐를 사용하여 문제를 해결했다.

문제 설명을 보면, 가장 낮은 스코빌 지수, 두번째로 낮은 스코빌 지수 * 2 의 합으로 새로운 스코빌 지수를 만들어 낸다.

모든 스코빌 지수가 기준 K 이상이 되면 섞은 횟수를 리턴한다.
스코빌 지수가 K 를 넘지 못하면 -1을 리턴한다.

즉, 힙 구조에서 루트 노드를 A 로, 다시 정렬된 힙 구조에서 또 한 번 루트 노드를 B 로 두어 문제를 해결한다.

힙의 길이가 1이 되는 순간, 루트 노드가 K 를 넘지 못하면 -1을 리턴.

코드.

def solution(scoville, K):
    answer = 0

    scoville.sort()

    import heapq

    heapq.heapify(scoville)

    while scoville[0] < K and len(scoville) > 1:
        A = heapq.heappop(scoville)
        B = heapq.heappop(scoville)

        heapq.heappush(scoville, A + B*2)
        answer += 1

    if scoville[0] < K:
        return -1

    return answer