[LeetCode/Easy] 2558. Take Gifts From the Richest Pile

1. Input

1) int[] gifts

2) int k

 

2. Output

1) 아래와 같은 단계를 거치고 남은 선물의 수의 합을 반환

- 선물의 수가 가장 큰 더미를 고른다.

- 가장 큰 더미가 여러 개라면 아무거나 하나를 고른다.

- 더미의 수의 제곱근만큼만 남겨놓고 나머지는 가져간다.

- 위 행동을 k번 반복한 후 남은 선물의 수를 더한다.

 

3. Constraint

1) 1 <= gifts.length <= 10^3

2) 1 <= gifts[i] <= 10^9

3) 1 <= k <= 10^3

 

4. Example

Input: gifts = [25,64,9,4,100], k = 4 -> Output: 29

설명:

- 100이 가장 큼 -> 루트100 = 10 -> gifts = [25,64,9,4,10]

- 64가 가장 큼 -> 루트64 = 8 -> gifts = [25,8,9,4,10]

- 25가 가장 큼 -> 루트25 = 5 -> gifts = [5,8,9,4,10]

- 10이 가장 큼 -> 루트10 = 3.xx -> gifts = [5,8,9,4,3]

- 5+8+9+4+3=29를 반환한다.

 

5. Code

1) 첫 코드(2023/03/02)

for(int i=0 ; i<k ; i++){
    Arrays.sort(gifts);
    gifts[gifts.length-1] = (int)Math.sqrt(gifts[gifts.length-1]);
}
long answer = gifts[0];
for(int i=1 ; i<gifts.length ; i++)
    answer += gifts[i];
return answer;

- 성능이 진짜.. 5% 5%는 아니지

2) 너무 화가 나서 다시 해본 코드(2023/03/02)

Arrays.sort(gifts);
int max_index = gifts.length-1;
for(int i=0 ; i<k ; i++){
    gifts[max_index] = (int)Math.sqrt(gifts[max_index]);
    for(int j=0 ; j<gifts.length ; j++){
        if(gifts[max_index]<gifts[j])
            max_index = j;
    }
}
long answer = gifts[0];
for(int i=1 ; i<gifts.length ; i++)
    answer += gifts[i];
return answer;

- 메모리 사용량은 확실히 줄었지만, 런타임은 크게 좋아지지는 않았다.