프로그래머스 고득점 Kit - 더 맵게

Problem

https://school.programmers.co.kr/learn/courses/30/parts/12117

프로그래머스

• 모든 음식의 스코빌 지수를 K 이상으로 만들어야 한다.
• 스코빌 지수가 가장 낮은 두개의 음식을 아래 규칙에 맞게 섞어야 한다.
• 음식을 섞은 횟수를 반환해라.

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

 

Input  / Output Example

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

 

 

Solution

해당 문제를 풀기 위해서는 heap(힙)이라는 자료형에 대해 알아야 한다.

heap은 최댓값이나 최솟값을 빠르게 찾을 수 있는 완전 이진 트리이다.

 

파이썬의 heapq ( heap 또는 priority queue ) 라이브러리를 사용해 쉽게 heap처럼 다룰 수 있다.

 

먼저 들어온 스코빌 리스트가 1보다 큰 동안 반복을 해줘야 한다.

가장 맵지 않은 음식이 K 이상이라면, 모든 음식이 K 이상이므로 반복문을 종료하고 섞은 횟수를 반환한다.

그렇지 않다면 음식을 규칙에 맞게 섞고, 다시 heap에 넣어준다.

Code

import heapq

def solution(scoville, K):
    answer = 0 # 섞은 횟수
    heapq.heapify(scoville)
    while len(scoville) > 1:
        s1 = heapq.heappop(scoville) # 가장 맵지 않은 음식
        if s1 >= K:
            break
        
        s2 = heapq.heappop(scoville) # 두번째로 맵지 않은 음식
        heapq.heappush(scoville, s1 + (s2 * 2))
        answer += 1
    if scoville[0] < K:
        return -1    
    return answer