👩‍💻 문제

🙋‍♀️ 답변

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
                
        // scoville 배열 heap에 넣어주기
        PriorityQueue<Integer> scovilleHeap = new PriorityQueue<>();
        
        for (int n : scoville) {
            scovilleHeap.add(n);
        }
        
        int count = 0;
        
        while(scovilleHeap.peek() < K) {
            if (scovilleHeap.size() < 2) {
                return -1;
            }
            int a = scovilleHeap.poll();
            int b = scovilleHeap.poll();
            int mix = a + b*2;
            
            scovilleHeap.add(mix);
            count++;
        }
        
        // while(!scovilleHeap.isEmpty()) {
        //     System.out.println(scovilleHeap.poll());
        // }
        
        return count;
    }
}

⭐️

• PriorityQueue scovilleHeap = new PriorityQueue<>();
  스코빌 지수를 새로 저장할 Heap을 생성한다.
• scovilleHeap의 최솟값이 K 미만일 경우 반복한다.
• scovilleHeap의 크기가 2 미만일 경우 새로운 스코빌 지수를 만드는 계산이 불가능 하니 -1을 리턴해준다.
• 최솟값 두 개 (a, b)를 scovilleHeap.poll()을 이용하여 꺼내준다. (꺼내고 scovilleHeap에서는 삭제된다)
• 새로운 스코빌 지수인 mix를 scovilleHeap에 다시 추가한다. -> 자동으로 오름차순 정렬이 된다.
• 카운트를 추가한다.
• scovilleHeap의 최솟값이 K 이상이 되면 (오름차순 정렬이기 때문에 모든 값이 K 이상이다), count를 반환한다.

🤔

PriorityQueue는 처음 사용해보는 것 같은데 자동 오름차순 정렬이 되니 편하다! Heap이라는 자료 구조에 대해 더 공부하고 정리해놔야겠다.