📖 문제

📝 풀이 과정1

1. 리스트 scoville을 내림차순으로 정렬한다.

   • scoville의 마지막 원소는 가장 안 매운 음식의 스코빌 지수가 된다.

   • 두 음식을 섞었을 때 리스트에서 하나의 요소를 삭제해야 한다. 이때 만약 오름차순으로 정렬한다면 index 0의 요소를 삭제해야하는데 리스트에서 index 0 의 요소를 삭제하면 O(N)의 시간이 걸린다.
     나름 시간 복잡도를 줄이기 위해서 내림차순으로 정렬했다.(ㅠㅠ)

2. scoville의 마지막 원소(가장 안 매운 음식의 스코빌 지수)가 K보다 작은 경우
   2-1. scoville에 원소가 하나밖에 없는 경우라면 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우이므로 return -1
   2-2. 스코빌 지수가 가장 낮은 두 개의 음식을 섞는다.(함수 new_scoville)
   2-3. 리스트 scoville을 다시 내림차순으로 정렬한다.

3. scoville의 마지막 원소(가장 안 매운 음식의 스코빌 지수)가 K보다 큰 경우

   • 모든 음식의 스코빌 지수가 K 이상이라는 것을 의미하므로 while문을 탈출한다.

⌨ 코드1 (heap 사용 X)

• 정확성 테스트는 통과하지만 효율성 테스트에서 통과하지 못했다.

# 두 음식을 섞어 새로운 음식을 만드는 함수
def new_scoville(scv1, scv2):
    return scv1 + (scv2 * 2)

def solution(scoville, K):
    answer = 0
    scoville.sort(reverse = True)
    
    while True:
        i = len(scoville) - 1
        # scoville의 마지막 원소(가장 안 매운 음식의 스코빌 지수)가 K보다 작은 경우
        if scoville[i] < K:
            # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
            if len(scoville) == 1:
                return -1
            # 스코빌 지수가 가장 낮은 두 개의 음식을 섞는다
            scoville[i - 1] = new_scoville(scoville[i], scoville[i-1])
            answer += 1
            scoville.pop()
            scoville.sort(reverse = True)
        # 모든 음식의 스코빌 지수가 K 이상인 경우
        else:
            break
            
    return answer

📝 풀이 과정2

• 로직은 풀이 과정1과 동일하다.
• 하지만 리스트 scoville을 그대로 사용하지 않고 heap에다가 저장한다.
  -> heap은 push, pop이 일어날 때마다 정렬작업을 알아서 해주기 때문에 풀이 과정1에서 했던 불필요한 정렬작업을 줄여줘서 시간복잡도 측면에서 좋다.

⌨ 코드2

import heapq

# 두 음식을 섞어 새로운 음식을 만드는 함수
def new_scoville(scv1, scv2):
    return scv1 + (scv2 * 2)

def solution(scoville, K):
    answer = 0
    # heap을 만들기 위한 리스트 생성
    scoville_heap = []

    # scoville에 있는 요소를 heap에 담는다.
    for s in scoville:
        heapq.heappush(scoville_heap, s)

    while scoville_heap:
        # 가장 안 매운 음식의 스코빌 지수
        first = heapq.heappop(scoville_heap)
        # 모든 음식의 스코빌 지수가 K 이상인 경우
        if K <= first:
            break
        # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
        # (하나 남은 음식의 스코빌 지수가 K 이하이다.)
        elif not scoville_heap:
            return -1
        # 두 번째로 안 매운 음식의 스코빌 지수
        second = heapq.heappop(scoville_heap)
        # 스코빌 지수가 가장 낮은 두 개의 음식을 섞는다.
        heapq.heappush(scoville_heap, new_scoville(first, second))
        answer += 1
    return answer

💡 새로 알게된 문법

기존 리스트를 힙으로 변환

• heapq.heapify(리스트)
• 예시

scoville = [1, 2, 3, 4, 5]
heapq.heapify(scoville)