[프로그래머스] 더 맵게(Lv2) - 힙(Heap)

문제

• 모든 음식 스코빌 지수 >= K로 만들기.
• 아래 방식을 반복하며 모든 음식의 스코빌 지수를 K이상으로 만든다.
  • 스코빌 지수 가장 낮은 음식 스코빌 지수 + (두 번째로 낮은 음식 스코빌 지수 *2)
• 만약 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없다면 -1 반환

---

• 입력값
  scoville[]: 스코빌 지수 담은 배열
  K: 목표 스코빌 지수
• 출력값
  스코빌 지수를 K로 만들기 위해 섞어야 하는 최소 횟수

  풀이

  스코빌 지수가 가장 낮은 음식 두 개를 섞어야 하기 때문에 최소힙을 사용하는 PriorityQueue를 이용한다.

1. PriorityQueue에 scoville[]을 넣는다.
2. 스코빌 지수가 K보다 낮은 음식이 있다면 마지막 1개의 음식만 남을 때까지 스코빌 지수가 가장 낮은 두 음식을 섞는다.
3. 섞은 횟수를 return || 마지막 음식이 남을 때까지 섞었는데 스코빌 지수가 K보다 작다면 -1 return

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : scoville)
            minHeap.add(num);

        int cnt = 0;
        while (minHeap.size() > 1 && minHeap.peek() < K) {
            minHeap.add(minHeap.poll() + (minHeap.poll() * 2));
            cnt++;
        }
        if (minHeap.size() == 1 && minHeap.peek() < K)
                return -1;
        return cnt;
    }
}

PriorityQueue에 scoville[] 삽입

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : scoville)
            minHeap.add(num);

두 음식 섞기

K보다 작은 음식이 있고 마지막 음식 1개만 남을 때까지 섞기

int cnt = 0;
while (minHeap.size() > 1 && minHeap.peek() < K) {
    minHeap.add(minHeap.poll() + (minHeap.poll() * 2));
    cnt++;
}

반환

섞는 작업이 끝났다면 스코빌 지수가 K보다 작은 값이 있는지 확인한 후 조건에 맞게 반환

if (minHeap.size() == 1 && minHeap.peek() < K)
                return -1;
        return cnt;