코딩테스트 - 더 맵게

저번엔 이분탐색을 활용한 문제를 살펴봤습니다. 이번엔 힙(Heap) 문제를 보죠.

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

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

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

모든 음식의 매운 정도가 일정 이상이 되면 되니까, 스코빌 지수가 가장 낮은 음식을 빠르게 찾아내서 그보다는 더 매운 음식과 섞어주는 과정을 반복하면 되겠네요. 언뜻 쉬워보이는 풀이지만, 결정적인 문제는 해결 시간에 있습니다. 가장 덜 매운 음식을 어떻게 빠르게 찾아낼까요? 섞은 음식을 집어넣고 나서는 그 순서는 어떻게 정할까요? 이럴 때 필요한 것이 최소 힙입니다.

힙은 기본적으로 완전 이진 트리입니다. 최소 힙은 자식 노드보다 부모 노드의 값의 크기가 항상 작습니다. 최소 힙의 root는 최소값을 가집니다. 최대 힙은 반대로 최대값을 가집니다. 최소 힙의 최소값을 참조할 때 시간복잡도는 루트를 딱 한 번 참조하므로 O(1)입니다. 값을 집어넣을 때에는 최악일 때 이진 트리의 높이만큼 원소를 바꿔주며, 트리의 높이는 밑이 2인 log 값을 가집니다. 따라서 삽입의 시간복잡도는 O(log n)입니다.

최대값 또는 최소값을 반복적으로 찾아야 하는 문제에서 힙을 활용하는 것은 꽤 효율적인 해답일 수 있습니다. 공간복잡도 또한 나쁘지 않은 게, 힙 정렬은 특성상 힙 자체의 크기를 벗어나는 별도의 공간을 할당하지 않으므로 임베디드에서도 활용도가 높은 편이죠.

문제는 JAVA로 풀었습니다. JAVA에서 최소 힙과 최대 힙은 PriorityQueue<E>로 구현되어 있습니다. 다음은 샘플 코드입니다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        for (int i : scoville) minHeap.add(i);
        
        int answer = 0;
        
        int n1, n2;
        while (true) {
            n1 = minHeap.poll();
            if (n1 >= K) break;
            if (minHeap.isEmpty()) {
                answer = -1; break;
            }
            n2 = minHeap.poll();
            minHeap.add(n1 + n2 + n2);
            answer++;
        }
        
        return answer;
    }
}

PriorityQueue는 기본적으로 오름차순 정렬이며, 최소 힙처럼 작동합니다. Enqueue와 Dequeue는 각각 add와 poll 메소드를 쓰면 됩니다. 최소값 또는 최대값을 조회하는 peek 메소드도 있긴 하지만 이 녀석은 값을 참조할 뿐 삭제하지 않습니다.

풀이 자체는 특별할 것이 없습니다. 가장 덜 매운 음식을 찾아 꺼내서 스코빌 지수를 확인합니다. 목표 지수보다 낮으면 두 번째로 덜 매운 음식을 꺼내서 섞은 후 다시 넣습니다. 그리고 과정을 반복합니다.

이 유형과 비슷한 - 따지고보면 좀 더 쉬운 - 피로도 지수 문제가 있는데요. 다양한 풀이 방법이 있겠습니다만 제곱값의 총합을 구한다는 점에서, 최대값이 작을수록 유리해지죠. 이를 응용하면 생각보다 쉽게 풀립니다.

Categories