1589. Maximum Sum Obtained of Any Permutation

We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 0-indexed.

Return the maximum total sum of all requests among all permutations of nums.

Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
Output: 19
Explanation: One permutation of nums is [2,1,3,4,5] with the following result: 
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3

Total sum: 8 + 3 = 11.
A permutation with a higher total sum is [3,5,4,2,1] with the following result:
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
Total sum: 11 + 8 = 19, which is the best that you can do.

 

Example 2:

Input: nums = [1,2,3,4,5,6], requests = [[0,1]]
Output: 11
Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].
Example 3:

Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
Output: 47
Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].

 

Constraints:
n == nums.length
1 <= n <= 105
0 <= nums[i] <= 105
1 <= requests.length <= 105
requests[i].length == 2
0 <= starti <= endi < n

 

첫 제출 코드

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        Map<Integer, Integer> freqMap = new HashMap<>();

        for(int [] req : requests) {
            int st = req[0];
            int en = req[1];

            for(int i = st; i <= en; i++) {
                freqMap.put(i, freqMap.getOrDefault(i, 0) + 1);
            }
        }

        List<Integer> values = new ArrayList<>(freqMap.keySet());
        Collections.sort(values, (a,b) -> (freqMap.get(b) - freqMap.get(a)));
        Arrays.sort(nums);

        // for(int val : values) {
        //     System.out.println("idx: " + val + " value: " + freqMap.get(val));
        // }

        int [] res = new int[nums.length];
        int idx = nums.length - 1;

        // 정렬된 nums를 거꾸로 돌면서 등장횟수가 많은 인덱스에 큰 값부터 넣어줌 
        for(int i = 0; i < values.size(); i++) {
            int newIdx = values.get(i);
            res[newIdx] = nums[idx];
            idx--;
        }

        // for(int i = values.size(); i < nums.length; i++) {
        //     res[i] = nums[idx];
        //     idx--;
        // }

        // for(int i = 0; i < nums.length; i++) {
        //     System.out.println(res[i]);
        // }

        int sum = 0;
        for (int [] req : requests) {
            int st = req[0];
            int en = req[1];
            for(int i = st; i <= en; i++) {
                sum += res[i];
            }

            sum %= 1000000007;
        }

        return sum;
    }
}

 

가장 많이 등장하는 인덱스를 Map에 저장을 해서 계산을 해주었지만, 최악의 경우 O(n^2)이 되어 시간초과가 나게 된다.

실제로 74/84에서 터지는 것을 확인할 수 있었다.

O(n^2)을 O(n)으로 줄이는 방법중에 하나는 누적 합 방식이다.

누적합에서도 차분 배열을 사용하면 시간 복잡도를 간단하게 줄일 수 있다.

requests = [[1,3],[0,1]]

이렇게 주어질 때,

freq[1]++, freq[4]--;

freq[0]++, freq[2]--; 와 같이 구간의 시작점을 증가시켜주고, 구간의 끝나는 지점의 + 1의 값을 감소시켜 준다.

 

for(int i = 1; i < n; i++) {
    freq[i] += freq[i-1];
}

 

그 뒤에, 구간의 누적합을 계산하여 최종값을 계산하면 우리가 원하는 값을 얻을 수 있다. 이 때의 시간 복잡도는 O(N)이다.

 

정답코드

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        int [] freq = new int[n];

        for(int [] req: requests) {
            int st = req[0];
            int en = req[1];
            freq[st]++;

            if (en+1 < n)
                freq[en+1]--;
        }

        // freq 빈도수를 저장 
        for(int i = 1; i < n; i++) {
            freq[i] += freq[i-1];
        }

        Arrays.sort(nums);
        Arrays.sort(freq);

        long sum = 0;
        for(int i = 0; i < n; i++) {
            sum += (nums[i] * (long) freq[i]);
            sum %= 1000000007;
        }
        return (int) sum;
    }
}

 

숫자가 너무 커서 overflow가 나서 좀 귀찮았다. 심지어 freq[i]도 int 범위를 넘어가는 케이스가 있어서 long으로 형변환을 해주었다. 

 

 

참고:
https://jypark1111.tistory.com/201

PrefixSum +1-1 기법 또는 차분 배열 기법(Difference Array Technique)