[프로그래머스] '더 맵게' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]

---

 

문제 설명

 

 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

 

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

알고리즘 분석

 

• 나의 풀이

import heapq as hq
def solution(scoville, K):
    answer = 0
    hq.heapify(scoville) # scoville을 heap 형태로 변형 
    while len(scoville) > 1: # scoville의 길이가 1보다 클 경우 반복 
        answer += 1	
        x, y = hq.heappop(scoville), hq.heappop(scoville) # 1, 2번째로 작은 숫자 
        more_spicy = x + y * 2 # 공식대로 연산 
        hq.heappush(scoville, more_spicy) # more_spicy를 scoville에 추가 
        if scoville[0] >= K: # scoville은 가장 작은 값이므로 K와 비교해서 더 클 경우 
            break
    else: # break가 실행되지 않았을 경우 
        return -1
    return answer

 

 

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게