매운음식 성애자(Way Cruel)

지난번 포스팅에서 이어집니다.

teus-kiwiee.tistory.com/60?category=924328

매운음식 성애자(Way Cool)

 

지난번, 단순 List를 사용해서, Scovile 지수가 원하는 값이 나올때까지 반복되는 매운음식 성애자 문제를 다뤘습니다.

 

하지만, 이때 List를 사용해서 효옹성 테스트를 지나가지를 못했습니다.

 

해당 문제에서는 Heap 구조를 사용해서 빠르게 Minimum 값을 찾는방법을 주요 메커니즘으로 사용합니다.

 

제가 Python으로 작성한 heap과 다르게,

 

Python 내장으로 clean code로 존재하는 heapq 패키지를 사용합니다.

 

해당 패키지를 사용하면, 특정 List에 heap 구조를 갖게 Element를 추가-삭제가 가능합니다.

 

아래는 heapq를 활용한 풀이법 결과입니다 :)

#heap을 사용하는 Python 내장함수
import heapq

def solution(scoville, K):
    #heap이라는 List를 사용해서 heap 구축
    heap = []    
    for i in scoville:
        heapq.heappush(heap, i)
    count = 0    
    while True:        
    	#가장 최소값을 pop한 후, 해당 값이 K보다 작은지 여부 판단
        temp1 = heapq.heappop(heap)
        if temp1>=K:
            break
        #temp1이 K보다 작으면, temp2는 의미가 없으므로 별도의 판별 X
        temp2 = heapq.heappop(heap)
        #heap에 두개를 섞은 새로운 스코빌을 추가합니다.
        heapq.heappush(heap, temp1 + temp2*2)
        count +=1
        if len(heap)==1 and heap[0]<K:
            count = -1
            break       
    
    answer = count
    return answer