3075. Maximize Happiness of Selected Children

문제

k번 happiness 배열을 훑으면서 남아 있는 가장 큰 값을 더해서 반환한다. 단, 한 번 가장 큰 값을 뽑으면 그 다음엔 배열에 담긴 모든 값이 1씩 줄어들고 그 상태에서 가장 큰 값을 또 꺼내야 한다.

나의 접근법

happiness를 오름차순 정렬하고, k개만큼 앞에서 가장 큰 값에서 인덱스를 뺀 값을 더해간다. 단, 가장 큰 값에서 인덱스를 뺀 값은 최소 0이다.

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        int n = happiness.length;
        for (int i = 0; i < n / 2; i++) {
            int temp = happiness[i];
            happiness[i] = happiness[n - i - 1];
            happiness[n - i - 1] = temp;
        }
        long result = 0;
        for (int i = 0; i < k; i++) {
            result += (happiness[i] - i < 0) ? 0 : happiness[i] - i;
        }
        return result;
    }
}

코멘트

시간복잡도는 코드 라인따라 계산해보았을 때, O(nlogn)이다. (Arrays.sort를 제외하면 O(n)이지만 최악을 시간복잡도로 하므로 Arrays.sort()의 O(nlogn)이 최악이므로 O(nlogn)이 된다.)