Programmers Coding Quiz #37 더 맵게!

문제 설명

매운 것을 좋아하는 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회입니다.

풀이

import heapq

def solution(scoville, K):
    result = []
    
    for v in scoville:
        heapq.heappush(result, v)
    
    count = 0

    while result[0] < K:
        heapq.heappush(result, heapq.heappop(result) + (heapq.heappop(result) * 2))

        count += 1

        if len(result) == 1 and result[0] < K:
            count = -1
            break
            
    return count

heapq모듈을 사용해 scoville을 리스트 힙으로 변환해줍니다.
heapq모듈을 사용하면 생성된 빈 리스트에 원소를 heapq.push로 밀어넣으면 최소힙으로 사용가능해집니다.
pop이나 push로 배열을 바꾸더라도 오름차순으로 재배열을 해줍니다. while을 통해 result[0] = 최소값이 K보다 작은 경우 heapush와 heappop을 사용해 제거와 새로운 원소추가를 동시에 해줍니다.
pop같은 경우엔 remove와 달리 '잘라내기'에 가깝기 때문에 연산값의 요소로 사용 가능합니다.

최소값 제거 -> (최소값이 제거되었으므로)두 번째 최소값 제거 -> 합산 값 추가

이와같은 세 번의 과정을 거치고 난 뒤 count를 1씩 증가시켜줍니다. while loop가 끝나고 누적된 count가 답이 됩니다.

물론 여기엔 문제조건에도 나와있는 예외의 경우가 존재합니다.
문제조건과 같이 계속해서 리스트 힙의 모든 요소를 연산과정을 거쳐 값을 올려도 K의 값에 미치지 못하는 경우입니다. 예컨데 [1, 2, 3] K= 15 일때처럼 1차 1 + 2 * 2 = 5 2차 3 + 5 * 2로 모든 요소를 다 쓰더라도 K에 못 미치는 경우입니다. 이 경우에는 연산이 끝나 단 하나의 원소가 남아 있는데도 K보다 작을 경우 count를 -1로 할당하고, while문을 강제종료 시켜버리면 됩니다.