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

gunny·2024년 8월 5일

leetcode 1508. Range Sum of Sorted Subarray Sums leetcode 1508. Range Sum of Sorted Subarray Sums python

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)을 차지한다.