[Java]LeetCode 1962. Remove Stones to Minimize the Total

문제 :

int 배열 piles[] 가 주어지고 임의의 배열 한 원소에 operation을 k번 수행해서 가장 작은 배열의 합을 만드는 것.

 ※ 한 element에 operation이 여러 번 수행될 수 있다.

operation = floor(piles[i] / 2)

 

Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.

---

문제 해결 법 :

      배열에서 가장 큰 값을 찾아서 그 값에 operation을 적용해주면 된다. -> 이 행동을 k번 수행하면 되는 것.

 

접근 : 

      ArrayList에 값을 넣고 sort해서 max 값을 찾은 후 , 함수 적용을 하고 업데이트를 해준다. 

 

문제점 : 

       ArrayList를 업데이트 해줄 때마다 다시 sort 해주어야 한다.

 

해결 : 

      항상 가장 큰 정수 값을 반환 해주는 Priority Queue 를 사용한다.

---

Priority Queue 선언 - 이 문제에서는 아래의 Queue를 선언해 사용했다.

// 낮은 int가 우선순위
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 높은 int가 우선순위
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

---

Queue에 piles[] 값 추가

for(int i: piles){
    pq.add(i);
}

---

k번, Queue가 비어있지 않을 때 반복 수행.

Queue 에서 값을 반환 받은 후, 값에 operation 적용.

다시 Queue에 삽입.

while(k > 0 && !pq.isEmpty()){
    int max = pq.poll();
    max = max - max/2;
    pq.add(max);
    k--;
}

---

결   과

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i: piles){
            pq.add(i);
        }

        while(k > 0 && !pq.isEmpty()){
            int max = pq.poll();
            max = max - max/2;
            pq.add(max);
            k--;
        }

        int sum =0;
        while(!pq.isEmpty()){
            sum += pq.poll();
        }
        return sum;
    }
}