문제 이해

LeetCode 2270번 Split Array Largest Sum과 유사한 조건으로, 배열을 두 부분으로 나누었을 때 왼쪽 구간의 합이 오른쪽 구간의 합 이상이 되는 분할 지점의 개수를 구하는 문제입니다.

길이가 n인 배열 nums에서 인덱스 i (0 ≤ i < n-1)를 기준으로 분할할 때, 다음 조건을 만족하면 유효한 분할입니다:

sum(nums[0..i]) ≥ sum(nums[i+1..n-1])

핵심 관찰

전체 합을 total이라 하면, 인덱스 i에서의 분할 조건은 다음과 같이 변형됩니다:

left_sum ≥ right_sum
left_sum ≥ total - left_sum
2 × left_sum ≥ total
left_sum ≥ total / 2

따라서 각 위치에서의 누적합이 total / 2 이상인지 확인하면 됩니다. 홀수 처리를 위해 올림 연산 (total + 1) // 2을 적용할 수 있습니다.

최적 접근: 단일 패스 누적합

Python의 itertools.accumulate를 활용하면 간결하게 해결할 수 있습니다. 배열의 마지막 원소는 제외해야 하므로 nums[:-1]로 슬라이싱합니다.

from itertools import accumulate
from typing import List

class Solution:
    def waysToSplitArray(self, arr: List[int]) -> int:
        threshold = (sum(arr) + 1) // 2
        return sum(prefix >= threshold for prefix in accumulate(arr[:-1]))

코드 상세 분석

동작 예시

입력: arr = [10, 4, -8, 7]

1. 전체 합: 10 + 4 + (-8) + 7 = 13
2. 임계값: (13 + 1) // 2 = 7
3. 유효 분할 지점 후보의 누적합: [10, 14, 6]
4. 조건 판별: [10≥7, 14≥7, 6≥7] → [True, True, False]
5. 결과: 2

대안 구현: 명시적 루프

accumulate 없이 직접 구현하면 다음과 같습니다:

from typing import List

class Solution:
    def waysToSplitArray(self, arr: List[int]) -> int:
        if len(arr) < 2:
            return 0
            
        total = sum(arr)
        running = 0
        valid_count = 0
        
        for idx in range(len(arr) - 1):
            running += arr[idx]
            if running * 2 >= total:
                valid_count += 1
                
        return valid_count

이 방식은 추가 메모리 없이 O(1) 공간 복잡도로 동작하며, accumulate를 사용하는 버전과 동일한 O(n) 시간 복잡도를 가집니다.

복잡도 분석

• 시간 복잡도: O(n) — 두 번의 선형 순회 (합 계산 + 누적합 검증)
• 공간 복잡도: O(1) 추가 공간 (accumulate 버전은 O(1), 누적합을 즉시 소비)

주의사항

음수가 포함된 경우에도 알고리즘은 정상 동작합니다. 누적합이 임계값을 넘었다가 다시 떨어질 수 있으므로, 모든 유효 위치를 검사해야 합니다. 또한 arr[:-1] 슬라이싱은 원본을 복사하므로 매우 큰 배열에서는 메모리를 고려하여 인덱스 기반 순회를 선택할 수 있습니다.