1508. Range Sum of Sorted Subarray Sums

[zeikar]

Problem link

https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/

Problem Summary

모든 subarray의 합을 정렬한 후 left부터 right 까지 합을 구하는 문제

Solution

그냥 문제 그대로 모든 subarray에 대해 합을 구한 후 정렬하면 된다. 당연하게도 합을 구할 때는 prefix sum으로 구해야 시간 안에 들어온다.

시간 복잡도는 정렬 때문에 O(n^2 log(n^2))

더 좋은 솔루션

sliding window, binary search를 쓰면 더 빨리 구할 수 있다.
특정값보다 작은 subarray 합의 개수와 그 합을 슬라이딩 윈도우로 구하고 left와 right에 대해 해당 지점을 이진 탐색으로 구할 수 있다.
값이 전부 양수이기 때문에 구할 수 있나 싶기도 하고 쉽지 않은거 같다. 이정도면 hard 난이도 아닌가... ㅋㅋ

솔루션 참고

Source Code

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        n = len(nums)
        prefixSum = [0] * (n + 1)

        for i in range(n):
            prefixSum[i + 1] = prefixSum[i] + nums[i]

        sums = []
        for i in range(n):
            for j in range(i, n):
                sums.append(prefixSum[j + 1] - prefixSum[i])

        sums.sort()

        ans = 0
        for i in range(left - 1, right):
            ans += sums[i]
            ans %= 1000000007
        return ans