문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

여러 더미에 있는 선물의 개수를 나타내는 정수 배열 gifts가 주어진다. 매초마다 다음을 수행한다.

• 선물이 가장 많이 쌓여있는 더미를 선택해라.
• 선물 개수가 최대인 더미가 여러 개라면, 그 중 아무거나 선택해라.
• 더미에 있는 선물의 개수를 원래 개수의 제곱근을 내림한 값으로 줄여라.

k초 후에 남은 선물 개수를 반환해라.

Example

#1
Input: gifts = [25, 64, 9, 4, 100], k = 4
Output: 29

#2
Input: gifts = [1, 1, 1, 1], k = 4
Output: 4

Constraints

• 1 <= gifts.length <= 10^3
• 1 <= gifts[i] <= 10^9
• 1 <= k <= 10^3

Solved

class Solution {
    public long pickGifts(int[] gifts, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());

        for(int gift : gifts){
            heap.add(gift);
        }

        for(int i = 0; i < k && heap.peek() > 1; i++){
            int x = heap.poll();
            heap.add((int) Math.sqrt(x));
        }

        long sum = 0;

        for(int h : heap){
            sum += h;
        }

        return sum;
    }
}