[프로그래머스][JAVA]Lv. 2 - 더 맵게

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

프로그래머스

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

---

문제를 풀기 위해서는 우선순위 큐를 알아야한다.

우선순위 큐는 이진 트리로 구성되어 있다.

노드가 제거되거나 새로운 노드가 추가되었을 때, 부모 노드와 자식 노드를 비교하여 우선순위가 더 높은 노드가 부모 노드가 되는 식으로 자리 교체가 일어난다.

루트 노드가 제일 큰 수가 되는 것을 max-heap, 그리고 작은 수가 되는 것을 min-heap이라고 하는데, 여기서는 min-heap을 이용할 것이다. 자바에서 기본 우선순위 큐는 min-heap으로 구성되어 있다. max-heap을 사용하려면 Comparator.reverseOrder()를 사용하면 된다.

PriorityQueue<Integer> min_heap = new PriorityQueue<>();
PriorityQueue<Integer> max_heap = new PriorityQueue<>(Comparator.reverseOrder());

 

이런 성질을 이용하여 우선순위 큐의 맨 앞에 최소값이 존재하도록 만들고, 최소값과 다음 값을 위의 조건에 따라 새로운 값으로 만들어 다시 우선순위 큐에 넣는것을 반복하여 문제를 해결하였다.

입출력 예시인 [1, 2, 3, 9, 10, 12]을 예로 들면

위의 값을 전부 우선순위 큐에 넣고 1과 2를 poll해주고 그 값으로 5를 만들어 다시 add해주었다.

그럼 우선순위 큐의 내부는 다음과 같아진다. [3, 5, 10, 12, 9]

다시 3과 5를 poll해주고 그 값으로 13을 만들고 다시 add해주면

[9, 12, 10, 13]과 같이 된다.

 

이렇게 우선순위 큐를 이용하여 우선순위 큐의 사이즈가 1만큼 작아지거나 최소값이 K보다 커질때까지 반복해어 문제를 해결했다.

우선순위 큐의 사이즈가 1까지 줄어들었는데 그 값이 K보다 작다면 -1을 return하도록 하였다.

import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < scoville.length; i++) {
            pq.add(scoville[i]);
        }

        while (K > pq.peek()) {
            answer++;
            if (pq.size() <= 1) break;
            int temp = pq.poll() + pq.poll()*2;
            pq.add(temp);
        }

        if (K > pq.peek()) {
            return -1;
        }

        return answer;
    }
}