[99클럽 4기 코테 스터디 TIL 22일차] 2558. Take Gifts From the Richest Pile (feat. 최대힙, Math.sqrt(), Math.floor())

1) 문제

https://leetcode.com/problems/take-gifts-from-the-richest-pile/

 

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

• Choose the pile with the maximum number of gifts.
• If there is more than one pile with the maximum number of gifts, choose any.
• Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

 

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can't take any pile with you. 
So, the total gifts remaining are 4.

 

Constraints:

• 1 <= gifts.length <= 103
• 1 <= gifts[i] <= 109
• 1 <= k <= 103

 

 

 

 

2) 내가 구현한 코드

import java.util.*;

class Solution {
    public long pickGifts(int[] gifts, int k) {
        long answer = 0L;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i=0; i<gifts.length; i++){
            pq.add(gifts[i]);
        }

        //제곱근 구하기: Math.sqrt(double a)
        //바닥 값 구하기: Math.floor(double a)
        for(int i=0; i<k; i++){
            int num = (int)Math.floor(Math.sqrt(pq.poll()));
            pq.add(num);
        }
        
        int size = pq.size();
        for(int i=0; i<size; i++){
            answer += pq.poll();
        }

        return answer;
    }
}

 

나는 제곱근의 바닥값을 구하기 위해 floor()를 사용 후 double인 갑을 int로 형변환시켰지만,

그럴경우 floor 없이 바로 int로 형변환하면 소수점 값들은 날아갈 것이다..

 

나는 힙의 사이즈를 미리 변수로 저장하고, 값을 누적했지만,

추가 구현 코드에서는 힙이 비어질 때까지 값을 누적했다...

 

나도 나중에 저렇게 사용해야지..~~!!!

3) 추가 구현 코드

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public long pickGifts(int[] gifts, int k) {

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int gift : gifts) {
            pq.offer(gift);
        }

        for (int i = 0; i < k; i++) {
            pq.add((int)Math.sqrt(pq.poll()));
        }

        long tot = 0;
        while(!pq.isEmpty()) {
            tot += pq.poll();
        }

        return total;
    }
}

 

 

4) 추가 문제

미들러 - 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

챌린저 - 산 모양 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스