[2024] day 218. Leetcode 1508. Range Sum of Sorted Subarray Sums

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 8월 4일 (일)
Leetcode daily problem

1508. Range Sum of Sorted Subarray Sums

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

Problem

n개의 정수로 이루어진 배열 nums가 주어질 때, 배열에서 비어 있지 않은 모든 연속 하위 배열의 합계를 계산한 다음 이를 내림차순으로 정렬하여 n * (n + 1) / 2 숫자의 새 배열을 생성했습니다.

새 배열에서 왼쪽 인덱스부터 오른쪽 인덱스(1부터 인덱스 지정)까지의 숫자 합계를 반환한다. 이 때 대답은 큰 숫자일 수 있으므로 10^9 + 7을 반환합니다.

Solution

binary search & sliding window

이 문제를 푸는 방법은
(1) brute force
(2) priority queue(우선순위 큐)
(3) binary search & sliding window(이진 분류 & 슬라이딩 윈도우) 로 풀 수 있다.

먼저 가장 쉽고 이해하기 쉬운 brute fore로 푸는 방법은
주어진 배열의 모든 부분 배열의 합을 계산해서 새로운 배열에 저장하고, 이 배열을 비내림차순으로(오름차순) 정렬하고 주어진 왼쪽 인덱스와 오른쪽 인덱스 사이의 요소들의 합을 구하는 방법이다.

Code

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

Complexicity

시간 복잡도

위 코드에서 for i in range(len(nums)) 에서 num의 길이에 해당하는 n번 실행되고 for j in range(i, len(nums)) 에서 내부루프는 최악의 경우 n번 실행 될 수 있어 O(n^2) 이다.

루프를 돌고 부분합을 저정한 sub_arr의 길이는 n(n+1)/2 이고, 시간복잡도는 O(n^2/2 log n^2/2)로 O(n^2 logn)이다.
범위의 합은 right-left+1 번 실행되어 n^2와 비례한다.
즉, 부분 배열의 합을 계산하고 범위의 합을 계산할 때 O(n^2)
정렬시 O(n^2logn)으로 최종 시간복잡도는 O(n^2logn)이다.

공간 복잡도

공간복잡도로는 모든 부분 배열의 합을 저장하므로 배열의 크기 n(n+1)/2으로 O(n^2)을 차지한다.

priority queue, binary search + sliding window로 최적화 하는 방법은 다음에 추가 !
생각보다 이해가 안돼서 천천히 봐야겠다