파이썬으로 왼쪽과 오른쪽 요소의 합이 같은 인덱스 찾기

nums라는 숫자 리스트가 주어졌을 때, 특정 인덱스 i를 기준으로 왼쪽에 있는 숫자들의 합과 오른쪽에 있는 숫자들의 합이 서로 같아지는 가장 작은 인덱스를 찾는 것이 이번 문제의 목표입니다. 만약 조건을 만족하는 인덱스가 존재하지 않는다면 -1을 반환하면 됩니다.

예를 들어 입력이 nums = [8,2,3,6,5,2,5,9,1,2]라고 해보겠습니다. 이 경우 정답은 4입니다. 인덱스 4를 기준으로 왼쪽 요소들은 [8,2,3,6]으로 합이 19이고, 오른쪽 요소들은 [2,5,9,1,2]로 합 역시 19이기 때문입니다.

문제 해결 접근 방법

매번 왼쪽 합과 오른쪽 합을 새로 계산하면 비효율적입니다. 대신 전체 합을 미리 구해두고, 리스트를 한 번만 순회하면서 오른쪽 합에서 현재 값을 빼고 왼쪽 합에 더하는 방식으로 O(n) 시간 복잡도 안에 효율적으로 해결할 수 있습니다.

• r := nums의 모든 요소의 합으로 초기화
• l := 0으로 초기화
• 각 인덱스 i와 값 x에 대해 반복:
  • r := r - x (현재 값을 오른쪽 합에서 제외)
  • 만약 r == l이라면 i를 반환
  • l := l + x (현재 값을 왼쪽 합에 추가)
• 끝까지 조건을 만족하는 인덱스를 찾지 못하면 -1 반환

구현 예제

다음 코드를 통해 실제 동작을 확인해 보겠습니다.

def solve(nums):
   r = sum(nums)
   l = 0
   for i, x in enumerate(nums):
      r -= x
      if r == l:
         return i
      l += x
   return -1

nums = [8,2,3,6,5,2,5,9,1,2]
print(solve(nums))

입력

[8,2,3,6,5,2,5,9,1,2]

출력

4

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 두 개의 변수(l, r)만 사용하므로 공간 복잡도는 O(1)입니다. 누적합(prefix sum) 개념을 활용한 대표적인 최적화 기법으로, 배열 관련 균형점(balanced point) 문제에서 널리 사용됩니다.