(Python3) - LeetCode (Medium) : 2270. Number of Ways to Split Array

https://leetcode.com/problems/number-of-ways-to-split-array

prefix sum 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. length 선언 후 nums의 길이를 저장합니다.

2. 누적합을 저장할 배열 sums를 선언 후 length만큼 0으로 초기화합니다.

 

3. valid_splits를 선언 후 0으로 초기화합니다.

 

4. sums의 누적합을 구해 갱신해줍니다.

📔 풀이과정

0에서 length - 2까지 for loop를 수행하며 split된 left_sum, right_sum을 구해줍니다. 0부터 i까지의 합이 sum[i], i+1부터 끝까지의 누적합은 sum[length-1] - sum[i]가 되므로 O(n)만에 valid 한 splits인지 구할 수 있습니다.

📔 정답 출력 | 반환

valid_splits를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        length = len(nums)
        sums = [0] * length
        sums[0] = nums[0]
        valid_splits = 0
        for i in range(1, length):
            sums[i] = nums[i] + sums[i-1]
        for i in range(0, length-1):
            left_sum = sums[i]
            right_sum = sums[length-1] - sums[i]
            if left_sum >= right_sum:
                valid_splits += 1
        return valid_splits

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.