프로그래머스 더 맵게

문제 설명

매운 맛에 대한 배열 scoville 이 주어지고, 최소한의 매움 지수인 K가 주어진다

가장 안 매운 값 2개를 "섞어" 서 특정 값으로 바꾸는 연산이 가능하다

new = alpha + (beta *2). 이때 alpha 가 가장 작은 값, beta가 2번째로 작은 값

이렇게 "섞기"를 통해 매움 지수가 K를 넘기도록 하고, 이에 필요한 연산의 수를 구하는 것

어떻게 해도 구할 수 없다면 -1 을 결과를 출력

 

문제 풀이

힙(Heap) 을 사용하면 쉽게 풀어줄 수 있다.

우리가 접근해야 하는 것은 리스트 전체가 아니라 "최소값" 이므로, 이에 대해 접근하기 위한 Heap 자료구조 사용

python 에서는 heapq를 써서 쉽게 처리할 수 있다.

 

우선 해당 문제에서는 while 문을 돌면서 최소값 2개를 뽑아서 섞고, 이후 최소값이 K를 넘는지 확인하도록 처리

 

 

코드

import heapq as hq

def solution(scoville, k):
    answer = 0
    hq.heapify(scoville)    
    is_smaller = True
    cnt = 0

    while(is_smaller and len(scoville) >=2):
        alpha = hq.heappop(scoville)
        beta = hq.heappop(scoville)
        gamma = alpha + (beta*2)
        hq.heappush(scoville, gamma)
        cnt = cnt +1
        
        test_value = scoville[0]
        if test_value >=k:
            is_smaller = False
            break
        
    answer = -1 if is_smaller else cnt
    return answer

기타

Heap은 우선순위 큐 구현을 위한 자료구조로 사용됨

예를 들어 방금 문제 같은 경우, 가장 작은 값이 최고의 우선순위를 가지니깐 그렇게 접근한 것