Programming/Algorithm
[프로그래머스] 더 맵게 (by Python)
oranz.23
2021. 5. 16. 03:36
문제
https://programmers.co.kr/learn/courses/30/lessons/42626
코딩테스트 연습 - 더 맵게
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같
programmers.co.kr
풀이
import heapq
def solution(scoville, K):
count = 0
scoville.sort()
while len(scoville) != 1:
temp = heapq.heappop(scoville) + 2 * heapq.heappop(scoville)
heapq.heappush(scoville, temp)
count += 1
if scoville[0] >= K:
return count
return -1
스코빌 지수를 담은 array가 정렬되어있다고 가정했을 때, 가장 작은 2개로 제시된 알고리즘을 계속 진행해주면 된다. 다만, 정렬되어있는 상태를 유지하는 것이 어려울 수 있다. 가장 작은 2개로 알고리즘을 수행하고 새로 생성된 음식의 스코빌 지수를 array에 넣어줄 때 그 순서를 알 필요가 있기 때문이다. 이를 처리하기 쉽게 하기 위해 heap을 차용하는 것이 핵심 아이디어.