[LeetCode] 1508. Range Sum of Sorted Subarray Sums

https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/description/?envType=daily-question&envId=2024-08-04

leetcode - Range Sum of Sorted Subarray Sums

문제 유형 : 정렬, 부분합

문제 난이도 : Medium

 

문제

You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10⁹ + 7.

 

n개의 정수가 들어있는 정수 배열 nums를 받습니다.

모든 길이가 1이상인 부분배열들의 합들로 배열을 만들어서 비내림차순으로 정렬하고, left ~ right(index-1기준)으로 합한 값을 반환하시오.

값이 커질 수 있기에, 1e9+7로 나눈 나머지를 반환하시오.

 

풀이

부분배열들의 합을 저장하는 길이가 n * (n+1)/2인 배열을 만든다.

배열을 정렬해서 left-1 ~ right-1의 범위의 수를 누적해서 반환한다.

 

부분합으로 부분배열들의 합을 구하는 더 효율적인 방법이 있지만, 어차피 정렬해야 하므로 원시적인 방법으로 만들어도 상관없다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        vector<int> newNums;
        for(int i = 0; i < n; i++) {
            int sum = 0;
            for(int j = i; j < n; j++) {
                sum += nums[j];
                newNums.push_back(sum);
            }
        }

        long long ans = 0;
        sort(newNums.begin(), newNums.end());
        for(int i = left-1; i < right; i++) {
            ans += newNums[i];
        }

        return ans % (int)(1e9 + 7);
    }
};