TIL - algorithm - heap(1)

문제 설명

매운 것을 좋아하는 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, 2, 3, 9, 10, 12]	7	2

풀이

• 아래는 문제 풀이를 위해 처음 작성했던 코드다. 결론부터 말하자면, 이 코드는 정답 도출하는 데는 문제가 없었지만, 효율성 테스트를 통과하지 못했다. 효율성이 낮았던 원인은 while loop에서 반복되는 sort() 메서드 때문이었다. sort() 메서드의 시간 복잡도는 O(N Log N)(1회 정렬 시)에 해당하는데, 이는 O(N)보다도 큰 수치다.

• sort()메서드를 사용한 이유는 배열 scoville에서 가장 작은 값과, 두 번째로 작은 값을 찾기 위해서였다. 낮은 효율성 문제를 해결하려면, sort()보다 작은 시간복잡도로 배열의 최솟값을 구하는 방법을 찾아야 했다.

def solution(scoville, K):
    answer = 0
    scoville.sort()
    
    while scoville[0] < K and len(scoville) >= 2:
        
        new_scoville_idx = scoville[0] + scoville[1]*2
            
        scoville[:2] = [new_scoville_idx]
        
        scoville.sort()
        
        answer += 1
        
    if len(scoville) < 2 and scoville[0] < K:
        answer = -1
        
    return answer

• 해결의 실마리는 자료구조(heap)에 있었다. heap은 완전 이진 트리(노드를 삽입할 때 왼쪽부터 차례대로 추가되는 이진 트리. 마지막 레벨을 제외하고는 모든 자식 노드가 채워져있는 트리) 중 하나로, 여러 개의 값들 중 최댓값 또는 최솟값을 빠르게 찾아내기 위해 고안된 자료구조다. heap을 활용하면 시간 복잡도 O(LogN)(1회 탐색 시)으로 트리에서 최솟값/최댓값을 찾거나, 특정 값을 트리에 추가할 수 있다.

  • 특정 배열을 heap 형태로 변환하는 경우 걸리는 시간복잡도는 O(N)이다.

• heap을 활용하기 위해선 heapq라는 모듈을 불러와야 한다. heap 자료 구조를 활용하면 아래와 같은 코드가 완성된다.

import heapq

def solution(scoville, K):
    answer = 0
    
    heapq.heapify(scoville) # 배열 scoville를 heap 형태(최소 heap)로 변환
    
    while len(scoville) >= 2:
        
        min_1 = heapq.heappop(scoville) # heap 자료구조에서 최솟값을 탐색 후 제거
        
        if min_1 >= K:
            break
            
        min_2 = heapq.heappop(scoville) # heap 자료구조에서 두 번쨰로 작은 값을 탐색 후 제거
        
        new_value = min_1 + min_2*2
        
        heapq.heappush(scoville, new_value) # 섞은 음식의 스코빌 지수를 기존 heap 구조에 삽입
        
        answer += 1
        
    if (len(scoville) < 2) and scoville[0] < K: # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에 대한 예외 처리
        answer = -1
        
    return answer

reviews

• 배열에서 최소값/최댓값을 찾아서 제거하는 경우, 효율성을 높이려면 sort(), min(), max()를 사용하기보단, heap 자료 구조를 이용하는 것이 좋다.

• 정렬 메서드 sort()가 시간 복잡도가 큰 메서드에 해당하므로, 사용 횟수를 최소한으로 제한하는 것이 성능면에서 좋다.