더 맵게

코딩테스트 연습 - 더 맵게 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 더 맵게

풀이)

모든 음식이 K수치 이상으로 매워야 하는데 이는 정렬되어 있는 음식 리스트에 대해 가장 낮은 수치의 음식이 K수치 이상이라면 만족된다. 음식 리스트를 맵기에 따라 오름차순으로 정렬해놓고 위 조건이 만족되는지 판단한다.

음식이 하나 남았는데 이 음식의 맵기가 K보다 낮으면 -1을 리턴하면된다.

위와 같이 매번 정렬을 해야하는 상황은 시간초과를 낸다. 따라서 자동으로 낮은 원소값부터 push되는 heapq를 이용해야 한다.

코드)  

import heapq

def solution(scoville, K):
    answer = 0
    count = 0
    heapq.heapify(scoville)
    while True:
        if len(scoville) == 1: # 음식이 하나 남았을 때
            if scoville[0] < K: # 남은 음식이 K이상 매운지
                answer = -1
                break
        if scoville[0] >= K: # 
            answer = count
            break
        else:
            value = 0
            value += heapq.heappop(scoville) 
            value += heapq.heappop(scoville) * 2
            heapq.heappush(scoville, value)
            count+=1

       
    return answer