문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

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

입출력 예

scoville K return [1, 2, 3, 9, 10, 12] 7 2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

접근 방법

본인은 파이썬의 heapq 라이브러리를 사용해본 적이 없었다. 그래서 sort 함수를 사용하여 구현해 보았다. 결과는 당연히 효율성 테스트 0점이 나왔다. 그래서 heapq 라이브러리에 대해 조금 알아보고 다시 풀어보았다.

우선 힙(heap)은 우선순위큐와 비슷하다고 생각하면 된다. 자동으로 가장 앞에 작은 수를 가져다 놓게 된다.

• scoville를 힙으로 바꿔준다.
• scoville[0]이 K이상이 되기 전까지 반복하도록 while문을 작성한다.
• while문 안에서 가장 작은 수와 두번째로 작은 수를 찾아 주어진 식을 대입한다.
• scoville의 길이가 1이 되었을 때, 가장 앞의 수가 K보다 작다면 이는 만들 수 없는 힙이므로 -1을 return한다.

가장 작은 수와 두번째로 작은 수를 찾아 주어진 식에 대입하는 과정에서 오답이 발생하였다. 그 이유를 찾아본 결과, heap은 가장 작은 수를 가장 앞에 가져오지만 두번째 인덱스라고 해서 두번째로 작은 수가 온다는 보장이 없다는 것을 알았다. 그래서 그 부분을 다시 한번 작성하였다.

• 처음에는 heapq.heappush(scoville, scoville[0] + (scoville[1] *2)) 으로 작성하였다.
• 이를 heapq.heappush(scoville, heapq.heappop(scaville) + heapq.heappop(scaville)*2)로 변경하였다.
• 이 과정에서 pop이 2번 이뤄지므로 따로 pop하는 과정은 삭제하였다.

solution.py

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