[프로그래머스] 더 맵게(python)

문제

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

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

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 합니다.

 입출력 예

 

 

 

 

 

 

풀이

 이 문제는 각각의 스코빌지수와 일정한 공식을 이용하여 새로운 스코빌지수를 계산하여 몇 번 반복해야 기준이 되는 스코빌 지수를 넘는지 반복 횟수를 구하는 문제입니다. 

여기서  (가장 맵지 않은 스코빌지수) 와 (2번째로 맵지 않은 스코빌지수) 를 이용하여 새로운 스코빌지수를 구한다고 되어있었고, 다음과 같이 풀이를 하면 되겠다고 생각했습니다. 

 

1. 최초 리스트를 오름차순으로 정렬한다.

2. 정렬한 리스트의 0번째 값과 1번째 값을 이용하여 섞었을 때의 새로운 스코빌지수를 계산한다. 

3. 0번째 값을 pop 해주고, 1번째 값은 새로운 스코빌지수의 값으로 바꾼다.

4. 이 과정을 모두 마쳤으면 다시 리스트를 정렬하고, 위의 과정을 반복한다.

 

이렇게 풀이 순서를 정리하였고, 정리한 내용을 토대로 작성한 소스코드는 아래와 같습니다.

def solution(scoville, K):
    answer = 0
    mix_scoville = 0
    
    while min(scoville)<K:         # 스코빌지수 최소값이 K보다 크면 종료
        if(len(scoville)<2):       # 스코빌지수가 2개는 남아있어야 계산 가능
            return -1
        scoville.sort()            # 반복될때마다 오름차순으로 정렬
        mix_scoville = scoville[0] + (scoville[1]*2)
        scoville.pop(0)
        scoville[0] = mix_scoville
        answer +=1

        
    return answer

 

 당연히 정답일줄 알고 채점을 했으나......

 

정확성 테스트는 모두 통과한 것에 비해, 효율성 테스트는 모두 통과하지 못했습니다... 정확한 이유는 모르겠으나, 아마도 반복할 때마다 오름차순으로 정렬해서 그런것이 아닐까 생각합니다.

 

그래서 다른 풀이들을 참고해보니 heapq 모듈로 풀이한 문제들이 많았고, heapq 모듈을 찾아보니 정의는 다음과 같았습니다.

 

"이 모듈은 우선순위 큐 알고리즘이라고도 하는 힙(heap) 큐 알고리즘의 구현을 제공합니다.

 이러한 heapq 모듈은 다양한 함수를 제공하지만 이 문제 풀이를 위해 필요한 함수에 대한 설명은 다음과 같습니다.

 1. heappush(heap, item) : 힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

 2.  heappop(heap) : 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 

 3. heapify(x) : 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

 

이 함수들을 이용하여 풀이를 하고자 한다면 다음과 같이 할 수 있다고 생각되었습니다.

 

1. 최초의 scoville 리스트를 힙으로 변환한다.

2. 정렬한 리스트의 0번째 값과 1번째 값을 이용하여 섞었을 때의 새로운 스코빌지수를 계산한다. 

3. 이때 0번째와 1번째 값을 heappop을 이용해 pop 해준다.

4. 계산된 새로운 스코빌지수를 heappush를 이용해 push 한다. 

 

이때 새로운 스코빌지수를 push 한 후 정렬이 되어있으므로, 따로 정렬하는 과정이 필요하지 않습니다. 위의 과정을 소스코드로 나타내면 아래와 같습니다.

import heapq

def solution(scoville, K):
    answer = 0
    mix_scoville = 0
    heapq.heapify(scoville)         # 최초 리스트에서 힙 정렬
    
    while scoville[0] < K:          # 스코빌이 기준점 넘어가면 반복 종료
        if(len(scoville)<2):        # 스코빌 지수 하나 남았을 때 더 이상 불가하므로 -1 리턴
            return -1
        mix_scoville = heapq.heappop(scoville) + (heapq.heappop(scoville)*2)
        heapq.heappush(scoville,mix_scoville)           
        answer +=1                          
       # 그 외에는 스코빌 계산하면서 값 빼주고 나온값 push
        
    return answer

 

 

이렇게 풀이를 진행하면 정확성과 효율성 테스트를 모두 통과하는 것을 확인할 수 있습니다.