[프로그래머스] 더 맵게

문제 보기

이 문제는 힙 문제이다.

힙 자료구조를 사용해서 우선순위 큐를 구현하는 것이 문제의 의도이다.

 

문제를 푼 로직은 다음과 같다.

1. 주어진 스코빌 리스트를 힙으로 변경한다. (7~8번째 줄)
2. 문제에서 주어진 방식대로 음식 2개를 섞어 새로운 음식을 만들고, 이 때의 스코빌 지수를 추가한다. (11~15번째 줄)
3. 모든 음식의 스코빌 지수가 K보다 높아야하므로, 힙의 루트가 K보다 작을 동안(= 힙의 최소값이 K보다 커지면 모든 음식의 스코빌 지수가 K보다 크다) 반복한다. (9~10번째 줄)
4. 더이상 섞을 음식이 없고, 스코빌 지수가 K보다 낮다면 -1을 반환한다. (17~18번째 줄)

 

import heapq


def solution(scoville, K):
	answer = 0
	
	# make scoville list heap
	heapq.heapify(scoville)
	# while minimum of the heap is lower than K
	while scoville[0] < K:
		# mix 2 foods
		a = heapq.heappop(scoville)
		b = heapq.heappop(scoville)
		heapq.heappush(scoville, a + (b * 2))
		answer += 1
		
		if len(scoville) == 1 and scoville[0] < K:
			return -1
		
	return answer