greentea31's Note

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

풀이 과정

음식을 섞어가면서 모든 음식이 스코빌 지수 K 이상이 되도록 하는 최소 섞음 횟수를 구해주면 된다.

리스트를 정렬하고, 리스트의 맨 앞이 K 이하이면 리스트의 0번째, 1번째 원소를 섞고 리스트에 넣은 다음에 다시 정렬해주고... 이런 방법이 떠오르지만 이렇게 문제를 풀면 음식을 섞을 때 마다 O(NlogN)인 정렬 과정을 거쳐야 하고 문제의 해결 알고리즘의 시간복잡도가 O(N^2logN)이 되어서 효율성 테스트를 통과할 수가 없다.

파이썬 내장 모듈인 heapq를 불러와 스코빌 리스트를 최소 힙으로 만든 후, 힙의 맨 위에 있는 음식의 스코빌 지수가 K 미만이면 heappop() 2번 해서 섞어주고 heappush() 해주고 다시 힙의 맨 위를 살펴보는 과정을 반복하는 방법으로 문제를 해결해 줄 수 있다.

리스트를 heap으로 만드는 heapify()가 O(NlogN), heappush()가 O(logN), heappop()도 O(logN)이므로 힙을 활용하여 문제를 해결하면 O(NlogN) 알고리즘으로 문제를 해결할 수 있고, 효율성 테스트도 통과할수가 있게 된다.

소스 코드

import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while scoville[0] < K:
        if len(scoville) < 2:
            return -1
        bowl = []
        bowl.append(heapq.heappop(scoville))
        bowl.append(heapq.heappop(scoville))
        heapq.heappush(scoville, bowl[0] + 2*bowl[1])
        answer += 1

    return answer