210222 개발일지(77일차) - 프로그래머스 알고리즘 문제 "더 맵게" 풀이

문제는 아래와 같다.

접근법

가장 작은 음식들부터 섞는다고 했으니, heap을 사용하여 풀었다. 파이썬에서는 아래와 같이 내장모듈을 사용할 수 있다.

import heapq

코드 작성

import heapq

def solution(scoville, K):
    heapq.heapify(scoville) 	# heapify를 활용하여 주어지는 scoville list를 heap으로 만든다.
    answer = 0
    while scoville[0]<K and len(scoville)!=1:	# 최소 heap과 K를 비교하고, scoville의 길이도 확인해서 반복문을 실행해준다.
        pop_tmp1 = heapq.heappop(scoville)
        pop_tmp2 = heapq.heappop(scoville)
        insert_tmp = pop_tmp1 + pop_tmp2*2
        heapq.heappush(scoville, insert_tmp)
        answer +=1        
        if len(scoville)==1 and scoville[0]<K:	# 여기서 and 뒤에 조건을 생각해주지 않아서 처음에 틀렸었다!
            return -1

    return answer

유의할 점

파이썬에서 제공하는 heap은 최소 heap으로 구현돼어 있다는 것을 유의해야 한다.