2021.07.10

더맵게

문제

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

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

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

처음 작성한 코드

def solution(scoville, K):
    answer = 0
    while min(scoville) < K:
        scoville.sort()
        if min(scoville) < K:
            scoville.append(scoville[0] + scoville[1] * 2)
            del scoville[:2]
            answer += 1
        if len(scoville) == 1 and min(scoville) < K:
            print(-1)
    return answer

코랩에서 실행했을 땐 별 문제없이 잘 실행되었다.
그런데 제출을 하려하니 런타임오류와 효율성테스트에서 실패했다고 떴다,,
같이 푸는 친구도 효율성테스트를 통과하지 못했다고 했다.

이리저리 찾아보고 알아본 결과
sort()가 반복적으로 수행되어 시간이 많이 소요되는 것 같았다.
그리고 heapq라는 함수를 사용하면 아주 간단하게 해결된다는 것도 알게 되었다.

수정한 코드

import heapq

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

    while len(scoville) >= 2:
        min_ = heapq.heappop(scoville) 

        if min_ >= K:
            return answer

        else:
            min_2 = heapq.heappop(scoville) 
            heapq.heappush(scoville, min_ + min_2 * 2)
            answer += 1
    
    if scoville[0] > K:
        return answer
    else:
         return -1

이것이코딩테스트다 5장 DFS/BFS 에서 잠깐 공부했었는데,
처음 공부했던터라 대충 이해하고 넘어갔었는데,,,

이번 문제를 통해서 사용법? 활용법?을 확실하게 알게되었다.