[2025] leetcode 2270. Number of Ways to Split Array

2025년 1월 3일 (금)
Leetcode daily problem

2270. Number of Ways to Split Array

https://leetcode.com/problems/number-of-ways-to-split-array/description/?envType=daily-question&envId=2025-01-03

0-인덱스로 시작하는 길이 n의 정수 배열 num이 제공될 때,
nums는 다음이 참인 경우에 인덱스 i에서 분할한다.

참인 경우
처음 i + 1개 요소의 합은 마지막 n - i - 1개 요소의 합보다 크거나 같다.

제약사항은 i 번째 인덱스에서 오른쪽에 요소가 하나 이상 있어야한다. 즉, 0 <= i < n - 1 이다.

이 때, 제약사항을 기반으로 참인 경우에 유효한 분할 수를 반환한다.

Solution

prefix sum

주어진 배열을 처음부터 n-1 까지 이동하면서, 해당 인덱스에서 분할을 한다고 가정 했을 때 왼쪽 원소의 합, 오른쪽 원소의 합을 연산해가면서 값을 비교해서 카운팅한다.

처음에는 right_sum을 전체 합에서 빼는 식으로 하니까 시간복잡도에서 걸렸는데, 애초부터 왼쪽합을 0, 오른쪽합을 전체 배열의 합으로 시작해서 왼쪽합은 더해나가고 오른쪽 합은 빼나가면서 연산했더니 Time Limit Exceeded 에 걸리지 않았다.

Code

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        ans = 0
        left_sum, right_sum = 0, sum(nums)

        for i in range(len(nums)-1):
            left_sum += nums[i]
            right_sum -= nums[i]

            if left_sum >= right_sum:
                ans+=1

        return ans![](https://velog.velcdn.com/images/heyggun/post/9dd4f483-9099-4f53-a7e3-adf4db014782/image.png)

Complexicity

시간 복잡도

배열을 한 번 순회하면서 왼쪽 합과 오른쪽 합을 연산하므로 시간복잡도는 O(n)이 소요된다.

공간 복잡도

count, left_sum, right_sum 변수에 상수를 저장하므로 모두 상수 공간이 필요하여 공간 복잡도로 O(1)이 필요한다.