Range Sum of Sorted Subarray Sums[M,Array,Two Pointers,Binary Search,Sorting]

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

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 109 + 7.

 

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13. 

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

 

Constraints:

• n == nums.length
• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 100
• 1 <= left <= right <= n * (n + 1) / 2

1. Python

 

이여... 웬열 ㅋㅋ 한 방에 PASS했다. 물론 소요시간은 꼴찌하긴 했다만..ㅎㅎ

 

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        modulo = 10**9 + 7
        
        i = 1
        ans = []
        while i <= n:
            for j in range(n-(i-1)):
                num = sum(nums[j:j+i])
                ans.append(num)
            i += 1
        ans.sort()
        
        return sum(ans[left-1:right]) % modulo

 

보통 for문을 많이 쓰네 아래처럼

while문이 time 측면에서 제일 안 좋은 문구인 거 같다. by 경험상

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        modulo = 10**9+7
        ans = []

        for i in range(n):
            ans.append(nums[i])
            num = nums[i]
            for j in range(i+1,n):
                num += nums[j]
                ans.append(num)
        
        ans.sort()
        return sum(ans[left-1:right])%modulo

 

2. C

 

아.. C에서 하려니까 역시 잡다하게 선언해줘야 할 게 너무 많다.

 

Sort도 안 돼, swap도 안 돼, Container Method도 없어.. 아오!

 

int rangeSum(int* nums, int numsSize, int n, int left, int right) {
    int mod = pow(10,9)+7;
    // how to contain the element, how to sort
    int nsize = n*(n+1)/2;
    int ans[nsize];
    int idx=0;

    for(int i=0;i<n;i++){
        int num = nums[i];
        ans[idx++] = num;
        for(int j=i+1;j<n;j++){
            num += nums[j];
            ans[idx++] = num;
        }
    }

    // insertion sort sort
    for(int i=1;i<nsize;i++){
        int temp = ans[i];
        int j = i-1;
        while(j>=0 && ans[j]>temp){
            ans[j+1] = ans[j];
            j--;
        }
        ans[j+1] = temp; 
    }

    // ans
    int answer = 0;
    for(int i = left-1;i<right;i++){
        answer += ans[i];
    }

    return answer%mod;
}

 

이렇게 해줬더니 time limit이 걸렸다..

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
int rangeSum(int* nums, int numsSize, int n, int left, int right) {
    int mod = pow(10,9)+7;
    // how to contain the element, how to sort
    int nsize = n*(n+1)/2;
    int ans[nsize];
    int idx=0;

    for(int i=0;i<n;i++){
        int num = nums[i];
        ans[idx++] = num;
        for(int j=i+1;j<n;j++){
            num += nums[j];
            ans[idx++] = num;
        }
    }

    // insertion sort sort
    // for(int i=1;i<nsize;i++){
    //     int temp = ans[i];
    //     int j = i-1;
    //     while(j>=0 && ans[j]>temp){
    //         ans[j+1] = ans[j];
    //         j--;
    //     }
    //     ans[j+1] = temp; 
    // }
    qsort(ans, idx, sizeof(int), compare);
    // ans
    int answer = 0;
    for(int i = left-1;i<right;i++){
        answer += ans[i];
        answer %= mod;
    }

    return answer%mod;
}

q sort라는 것을 쓰면 좀 빠르긴 하다..

NlogN인 Quick Sort..!

 

3. C++

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        long long mod = pow(10,9)+7;
        vector<int> ans;
        for(int i=0;i<n;i++){
            int num = nums[i];
            ans.push_back(num);
            for(int j=i+1;j<n;j++){
                num += nums[j];
                ans.push_back(num);
            }
        }
        sort(ans.begin(),ans.end());
        long long answer=0;
        for(int i=left-1;i<right;i++){
            answer+=ans[i];
            answer%=mod;}
        return answer%mod;
    }
};