[99클럽 코테 스터디 25일차 TIL] 정렬

📖 오늘의 학습 키워드
정렬

오늘의 회고

문제

[Append K Integers With Minimal Sum]
https://leetcode.com/problems/append-k-integers-with-minimal-sum/description/

나의 해결

class Solution {
    public long minimalKSum(int[] nums, int k) {
        long answer = 0;
        int len = nums.length;
        long pre = 0;
        Arrays.sort(nums);
        for(int i = 0; i < len; i++){
            long diff = nums[i] - 1 - pre;
            if(diff > 0) {
                if(diff < k) {
                    answer += diff * 0.5 * (nums[i] + pre);
                    k -= diff;
                }
                else {
                    answer += k *  0.5 * (pre + k + pre + 1);
                    k = 0;
                }
            }
            if(k == 0) {
                break;
            }
            pre = nums[i];
        }
        if(k > 0) {
            answer += k *  0.5 * (nums[len-1] + k + nums[len-1] + 1);
        }
        return answer;
    }
}

1. 배열 nums를 오름차순으로 정렬한다.
2. i가 0부터 len(nums의 길이)-1까지 for 문을 돌며 새로 추가한 k개의 정수들의 합의 최솟값을 구한다.
3. nums[i]와 pre(직전 값) 사이의 정수의 개수를 구해 diff에 저장한다.
4. diff 값이 0보다 클 경우, diff가 k보다 작으면 nums[i]와 pre 사이의 모든 값의 합을 구해 answer에 더한다. 만약 k보다 크거나 같다면 pre와 pre+k 사이의 모든 값의 합을 구해 answer에 더한다.
5. k가 0이 되면 for 문을 빠져나온다.
6. pre 에 nums[i]을 저장한다.
7. for 문 실행 후에도 k가 0보다 크다면 nums[len-1](배열의 마지막 값)와 nums[len-1]+k 사이의 모든 값의 합을 구해 answer에 더한다.
8. answer를 반환한다.