[프로그래머스] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

---

 

문제 풀이

 

먼저 리스트 scoville을 heapify 함수를 사용해 힙으로 만들어줘야 한다.

 

가장 첫 번째 원소, 즉 scoville[0]은 항상 힙의 루트 노드로 최솟값이기 때문에

scoville[0]이 K 보다 크거나 같을 때까지 반복문을 돌려준다.

 

pop을 하지 않고 인덱스로만 비교해준다면 두 번째로 작은 값을 찾기 위해 세 번째 값까지 비교해야 하지만, 이 문제에서는 최솟값 2개를 뽑아 다시 push 해주는 방식이기 때문에 간단하게 풀 수 있다.

 

가장 작은 값, 두 번째로 작은 값을 찾기 위해 pop을 두 번 해주고, 문제에서 제공한 공식을 적용한 값을 push 해준다. 한 번 섞은 것이므로 answer를 하나 올려준다.

 

스코빌 지수를 K 이상으로 만들 수 없는 경우는 모두 섞어서 음식이 하나 남았는데도 그 음식의 스코빌 지수가 K 보다 작은 경우이므로 if 문으로 걸러준다. 

---

 

정답 코드

import heapq

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