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

문제 바로가기

코딩테스트 연습 - 더 맵게

파이썬 풀이입니다.

def solution(scoville, K):
    answer = 0
    heap = []

    for scov in scoville:
        heapq.heappush(heap, scov)

    while heap[0] < K:
        if len(heap) < 2:
            if heap[0] < K:
                return -1
            break

        first_min = heap[0]
        heapq.heappop(heap) 
        second_min = heap[0] 
        heapq.heappop(heap) 
        heapq.heappush(heap, mixFood(food1=first_min, food2=second_min)) 

        answer += 1

    return answer

def mixFood(food1, food2):
    return food1 + food2*2

먼저, heap 자료구조를 사용하기 위해 heapq 모듈을 import 해줍니다.

 

이후 heap 배열에 scoville배열을 heappush 해주어 heapify가 된 heap 배열을 만듭니다. (heapq는 기본적으로 min heap으로 정렬)

 

heapify가 된 array에서 0번째 인덱스의 값이 min value이므로 해당 값이 K보다 크거나 같을때까지 반복.

 

만약 음식을 섞으며 음식의 갯수가 2보다 작아졌을 경우는 더 이상 섞을 수 없고, 이 때 남은음식 중 가장 작은 스코빌을 가진 음식이 K보다 작을경우 K보다 큰 scoville을 만들 수 없으므로 -1 리턴.

 

가장 작은 스코빌을 가진 음식과, 두번째로 작은 스코빌을 가진 음식을 섞어서 나온 음식의 스코빌을 heap배열에 저장, 이 때 재료로 쓴 두 음식은 pop해줌.

 

음식을 섞을 때 마다 섞은 횟수(answer)를 1씩 증가

 

위의 예제에 주석이 포함된 소스코드는

여기 에서 보실 수 있습니다.