[프로그래머스] 42626 더 맵게 (python 파이썬)

프로그래머스

---

heap을 이용하는 문제. 되게 오랜만에 풀어본 유형이라 시간이 걸렸다.

여러 문제를 풀어보며 언제 heap을 쓰는 게 좋은지 연습해야겠다.

---

아이디어

문제를 해결하려면 scoville리스트에서 계속 가장 작은 값을 찾아서 return 해야 한다.

 

min() 메서드의 시간 복잡도는 O(N)이다. 문제에서 주어진 리스트의 길이 최대가 크기 때문에 좀 더 효율적인 방법을 찾아야 한다.

 

heap을 이용해서 우선순위 큐를 구현하면 시간을 단축할 수 있다. heappop의 시간 복잡도는 O(logN)이다.

---

전체 코드

import heapq

def solution(scoville, K):
    
    answer = 0
    
    heapq.heapify(scoville)
    
    while True:     
        first = heapq.heappop(scoville)
        
        if first >= K:
            break
            
        if len(scoville) <= 0:
            answer = -1
            break
        
        second = heapq.heappop(scoville)
        
        new_food = first + second * 2
        answer += 1
            
        heapq.heappush(scoville, new_food)
        
    return answer

---

코드 설명

    heapq.heapify(scoville)

일단 heapify함수를 사용해 scoville 리스트를 heap으로 변환해 주자.

 

while True:     
        first = heapq.heappop(scoville)
        
        if first >= K:
            break
            
        if len(scoville) <= 0:
            answer = -1
            break

heappop을 통해 scoville에서 가장 작은 값을 return 해준다.

 

문제 조건에서 모든 음식의 스코빌 지수가 K를 넘는지 확인해야 한다. 즉, 리스트에서 가장 작은 값만 비교해 봐도 확인이 가능하다.

 

그리고 모든 음식의 스코빌 지수가 K이상으로 만들 수 없는 경우는 -1을 정답으로 출력하라고 요구한다.

이 말은 조합을 계속해서 scoville리스트가 빈다면 -1을 출력해 주면 된다.

 

second = heapq.heappop(scoville)
        
new_food = first + second * 2
answer += 1
            
heapq.heappush(scoville, new_food)

위의 두 조건에 걸리지 않았다면 새로운 음식 조합을 위해 heappop으로 가장 작은 값(두 번째로 작은 값)을 뽑아주자.

 

문제에서 주어식 식으로 스코빌을 계산하고, 섞은 횟수 answer += 1을 해준다.

 

새로 만든 음식은 heappush를 통해 scoville 리스트에 삽입해 준다.

 

마지막으로 answer값을 출력해 주면 문제에서 요구하는 답이 된다.