99클럽 코테 스터디 3일차 TIL, Heap(더 맵게)

1. 문제 정의

2. 문제 접근

스코빌을 더해줄때 마다 더해준 스코빌이 그 값의 정렬에 따라 자동으로 들어가야 하므로 PriorityQueue를 쓰는것이 편할 것 같다.

3. 문제 풀이

1. PriorityQueue 를 이용하여 첫번째 스코빌과 두번째 스코빌을 빼내어 계산하여 다시 pq에 넣어준다.
2. 넣어줄때 마다 최소 스코빌 값을 갱신해준다.
3. 마지막에 반복된 횟수를 리턴해준다.

4. 코드

import java.util.*;

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

        for (int s : scoville) {
            pq.add(s);
        }
        
        int minVal = pq.peek();

        while (K > minVal && pq.size() > 1) {
            ans++;
            int firstS = pq.poll();
            int secondS = pq.poll();
            
            int sum = firstS + secondS*2;
            pq.add(sum);
            minVal = pq.peek();
            
        }
        
        if(K > minVal) return -1;
        
        return ans;
    }
}

5. 회고

PriorityQueue 를 쓸 경우 자동으로 오름차순으로 안에서 정렬을 해주기 때문에 편하다. 잘 활용해 보자.