문제 분류

  • 힙 알고리즘

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • scoville의 길이는 1 이상 1,000,000 이하입니다.
  • K는 0 이상 1,000,000,000 이하입니다.
  • scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

알고리즘 유도 과정

  1. 스코빌 지수가 담긴 배열을 힙 구조로 만든다.
  2. 힙에서 하나를 추출한 값(가장 맵지 않은 값)을 a라 하면, a가 K를 넘겼는지 확인한다. 넘겼으면 횟수를 반환하고 알고리즘을 종료한다.
  3. K를 넘기지 않았으면, 힙에서 하나를 더 추출(두번째 맵지 않은 값)하여 공식대로 계산한 뒤 다시 힙에 넣는다.
  4. 힙에 값이 하나가 남을 때 까지 2,3번 과정을 반복한다.
  5. 힙에 마지막 남은 값이 K를 넘지 않으면 -1, 넘었으면 횟수를 반환한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq

def solution(scoville, K):
    cnt = 0
    heapq.heapify(scoville)

    while len(scoville) > 1:
        a = heapq.heappop(scoville)
        if a >= K:
            return cnt
        b = heapq.heappop(scoville)
        heapq.heappush(scoville, a + b * 2)
        cnt += 1

    return -1 if scoville[0] < K else cnt

복잡도 분석

힙 구조를 생성 하는데 $O(nlogn)$ 만큼의 복잡도가 발생한다.

힙에서 삽입, 삭제하는데 $O(logn)$ 만큼의 복잡도가 발생한다.

한번의 과정에서 일반적으로 삭제 2번과 삽입 한번이 발생한다. $O(3logn \approx logn)$

최악의 경우 루프를 $n-1$회 수행하므로 $O((n-1) * 3logn \approx nlogn)$

힙구조 생성$(nlogn)$ + 루프$(nlogn)$ $\approx O(nlogn)$