Programmers, 힙(heap), ‘더 맵게’

프로그래머스 연습문제 중 42626번 ‘더 맵게’

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

문제설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. 입출력 예

입출력 예

scoville	K	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5 가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13 가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

---

풀이

처음 문제에 접근할때는 따로 힙을 활용하지 않고 스택을 활용 했는데, 효율성 테스트에서 탈락 되었다.

기존의 스택을 활용하는 방법은 새로운 스코빌 지수를 만들 때 마다 sort를 진행해서 입력이 커질수록 오래 걸릴 수 밖에 없던 코드 였다. 입력으로 주어지는 scoville의 최대 길이가 1,000,000 이므로 다른 방법이 필요했다.

그래서 이 문제의 특성인 단계마다 가장 맵지 않은 음식의 스코빌 지수와 두번째로 맵지 않은 스코빌 지수가 바뀐다는 특성을 고려했다. 이는 heapq 자료형을 이용하면 간단히 해결할 수 있다.

코드의 흐름은 다음과 같다.

1. 입력으로 주어진 scoville을 heapq 자료형인 heap에 순서대로 저장한다. (파이썬은 최소값 heap을 지원하므로 이 문제에 딱 적당하다)
2. heap의 최소값인 heap[0] < k 이거나 heap에 원소가 남아있는 동안 스코빌 지수 계산을 반복 진행하다.
3. 만약 계산중에 더 이상 heap에 원소가 남아있지 않다면, 마지막 원소를 가리키는 first의 스코빌지수가 k 이상인지 마지막으로 확인하고 결과를 return한다.

이를 코드로 작성하면 다음과 같다.

import heapq

def solution(scoville, K):
    answer = 0

     # heap 자료형을 저장할 배열 선언
    heap = []
    for s in scoville:
        heapq.heappush(heap, s)
    
     # heap의 root인 heap[0]이 K보다 작고, heap의 원소가 존재하는 동안 반복한다.
    while heap and heap[0] < K:
        first = heapq.heappop(heap)

         # heap 원소가 first 하나일때 처리
        if not heap:
            return -1 if first < K else answer
        second = heapq.heappop(heap)

         # 새로운 스코빌 지수를 계산하고,answer을 1증가시키며, 새로운 스코빌 지수를 추가한다.
        answer += 1
        new_scov = first + (second * 2)
        heapq.heappush(heap, new_scov)  
    
    return answer