[프로그래머스] 더 맵게

문제 링크

내 코드 ( 효율성 - 시간초과 )

def solution(scoville, K):
    answer = 0
    stack=[]
    scoville.sort(reverse=True)
    for i in scoville:
        stack.append(i)
    while 1:
        if min(stack)>=K:
            return answer
            break
        if len(stack)>=2:
            s = stack[-1]+stack[-2]*2
        else:
            return -1
            break
        stack.pop()
        stack.pop()
        stack.append(s)
        answer+=1
        stack.sort(reverse=True)

참고 코드 ( 통과 )

heapq를 사용함

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

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

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

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