[Python] 더 맵게 - 프로그래머스 Level2

문제 설명

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

 

나의 Solution

import heapq

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

 

다른 사람 Solution

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  

    return answer

 

 

hepq 사용 안한 풀이

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

 

알게된 사실

처음엔 heapq를 몰라서 그냥 sort 함수를 사용해서 풀어보았다. 하지만 바로 효율성에서 에러가 나 어떻게 푸는지 확인해보니 heapq를 사용하면 쉽게 풀이할 수 있다고 한다.

heapq 모듈은 힙(heap) 자료형이 있는데 힙(heap)은 이진트리로서 부모노드가 자식노드 보다 값이 작거나 같다! 그렇기에 heap함수는 리스트에서 가장 작은 요소나 큰 요소에 반복적으로 접근하는 작업에 유리하다

 

heapq.heapify(list)는 리스트 자료형을 힙 자료형으로 변환하는데 시간복잡도는 O(n)이다.

heapq.heappop(list) : 가장 작은 값을 호출하는 함수로서 항상 루트 노드 값을 꺼내온다. O(1)

heapq.heappush(list, item) : 힙에 새 항목을 추가하는 함수이며 시간복잡도는 O(logN)의 값을 가진다.