[알고리즘]프로그래머스: "더 맵게"

음식의 스코빌 지수가 들어있는 리스트 scovlle을 입력받는다 

가장 스코빌이 낮은 음식과 두번째로 낮은 음식을 섞에 새로운 스코빌의 음식을 얻는데 

섞인음식 mixed = 가장 낮은 스코빌 + 2*두번째로 낮은 스코빌이다. 

 

모든 음식이 K이상의 스코빌을 가지도록 이를 반복하고 

반복횟수의 최솟값을 return한다  

from heapq import heappush, heapify ,heappop


def solution(scoville, K):
    cnt =0 
    
    heapify(scoville)
    
    while scoville[0]<K:
        first =heappop(scoville)
        second=heappop(scoville)
        mixed = first + 2*second
        heappush(scoville, mixed)
        
        cnt+=1
        if len(scoville)==1 and scoville[0]<K:
            return -1

    
    
    return cnt

heap구조를 활용하였다. 

 

처음에는 정렬알고리즘과 deque의 popleft를 활용해 진행하였는데 

최악의 처음 n번의 정렬을 진행하기 때문에, 효율성 테스트에서 시간초과가 발생하였다. 

 

heap 구조를 활용해 추가적인 정렬없이(정확히는 heappush나 pop에서 정렬이 진행되지만)

진행하였을 때 시간초과 없이 성공할 수 잇었다.