[Java] 프로그래머스 : 더 맵게

문제 링크

프로그래머스

---

---

힙 트리(heap tree)를 사용하는 문제다. 입출력 예의 설명에 따르면 모든 음식의 스코빌 지수가 K이상이 되지 않았을 때는 문제의 조건에 따라 만들어진 새로운 음식도 섞이는 대상이 될 수 있다. 스코빌 지수가 가장 낮은 두 수를 지속적으로 뽑아내고 새로운 음식을 집어넣으면서 정렬을 해야하는데, 일반적인 배열이나 리스트를 사용하면 음식을 섞을 때마다 매번 정렬을 하게 되면 시간복잡도 상으로 굉장한 손해를 보게 된다. 따라서, 힙 트리를 사용하는 것이 바람직하다.

 

힙 트리 방식으로 동작하는 대표적인 자료구조로는 우선순위 큐(Priority Queue)가 있다. 본 문제의 경우에는 아래와 같은 과정을 통해 해결할 수 있다.

 

1. 우선순위 큐에 모든 스코빌 지수를 삽입
2. 우선순위 큐에서 값을 2개 꺼낸 후 주어진 조건에 맞게 계산
3. 계산 결과를 다시 우선순위 큐에 삽입
4. 1~3을 반복하다가 우선순위 큐의 가장 위 값이 K 이상일 경우 실행 종료

 

문제의 조건 상 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없을 경우엔 -1을 반환해야 한다. 우선순위 큐의 크기가 1이면 더 이상 음식을 섞을 수 없게 되는데, 이 때 마지막으로 남은 음식의 스코빌 지수가 K보다 작다면 더 이상 음식을 섞는게 불가능하므로 -1을 반환한다.

---

Code

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        for (int s : scoville) {
            heap.add(s);
        }

        while (heap.peek() < K) {
            heap.add(heap.poll() + heap.poll() * 2);
            answer++;
            // 더 이상 음식을 섞을 수 없고, 남은 음식의 스코빌 지수가 K보다 작으면 -1 반환
            if (heap.size() == 1 && heap.peek() < K) {
                answer = -1;
                break;
            }
        }

        return answer;
    }
}