[힙] 프로그래머스 Lv2. 더 맵게 - Python

🗂️ 문제

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

💡 접근법

해당 문제의 경우 리스트를 이용하면 시간 초과가 발생하므로 heapq 라이브러리를 사용해야 한다.

 

인자로 들어온 scoville 리스트를 heapify를 통해 힙 자료구조로 변환한다.

힙의 경우 0번 인덱스에 해당하는 값은 항상 힙 내의 값들 중 최소값이며 힙은 정렬 상태이다. 따라서 scoville[0]이 K보다 작을 경우에 스코빌 지수가 가장 낮은 두 개의 음식을 계산하여 힙에 다시 push해주고 섞은 횟수(answer)를 1 증가시킨다.

 

또한 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우를 고려해야 한다.

스코빌 지수가 K 미만인 음식에 대해 스코빌 지수를 다시 계산하고 힙에 push한 후 scoville 리스트의 길이가 1일 경우엔 더 이상 스코빌 지수의 값을 계산할 수 없다. 또한 해당 스코빌 지수의 값이 K보다 작다면 이는 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 케이스가 된다. 따라서 이 두 조건을 만족할 경우엔 -1을 return해야 한다.

 

😎 내 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while(scoville[0] < K):
        heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville)*2)
        answer += 1 
        if len(scoville) == 1 and scoville[0] < K:
            return -1
    
    return answer

 

 

🧐 배운 점

1. 조건에 만족하여 -1을 return할 때 answer에 -1을 대입하고 return answer하는 것보다 return -1을 하는 것이 더 가독성이 좋다.