문제 개요
정수로 이루어진 배열 A가 주어졌을 때, 이 배열을 합이 서로 같은 세 개의 비어 있지 않은 부분으로 나눌 수 있다면 결과는 true입니다. 그렇지 않다면 false를 반환합니다.
좀 더 형식적으로 표현하면, 인덱스 i+1 < j를 찾아 다음 조건을 만족할 때 배열을 세 부분으로 나눌 수 있습니다.
- 첫 번째 부분: A[0] + A[1] + ... + A[i]
- 두 번째 부분: A[i+1] + A[i+2] + ... + A[j-1]
- 세 번째 부분: A[j] + A[j+1] + ... + A[A.length - 1]
세 부분의 합이 모두 같아야 한다는 점이 핵심입니다.
예시
입력이 [0,2,1,-6,6,-7,9,1,2,0,1]이라면 출력은 true입니다. 실제로 배열을 다음과 같이 세 부분으로 나눌 수 있습니다.
- [0,2,1] → 합: 3
- [-6,6,-7,9,1] → 합: 3
- [2,0,1] → 합: 3
해결 방법
이 문제는 누적합(cumulative sum)과 두 포인터를 활용하면 효율적으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.
- 배열 전체의 합을 구하고, 이를 3으로 나눈 값을 required_sum(목표 합)으로 설정합니다. 만약 전체 합이 3으로 나누어 떨어지지 않으면 바로 false를 반환합니다.
- sum_left에는 왼쪽에서 오른쪽 방향의 누적합을 저장합니다.
- sum_right에는 오른쪽에서 왼쪽 방향의 누적합을 저장합니다.
- index1은 배열의 시작(0), index2는 배열의 끝(len(A) - 1)으로 초기화합니다.
- index1 < index2인 동안 다음을 반복합니다.
- sum_left[index1]이 required_sum과 같아질 때까지 index1을 증가시킵니다.
- sum_right[index2]가 required_sum과 같아질 때까지 index2를 감소시킵니다.
- 두 포인터가 유효한 위치에 도달했다면 true를 반환하고, 그렇지 않다면 false를 반환합니다.
전체 합이 3의 배수가 아니라면 세 부분의 합이 같을 가능성 자체가 없으므로, 초기 검사만으로도 불필요한 연산을 줄일 수 있습니다.
Python 코드 구현
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution(object): def canThreePartsEqualSum(self, A): temp = sum(A) if (temp % 3 != 0): return 0 sum_left = [0 for i in range(len(A))] sum_left[0] = A[0] sum_right = [0 for i in range(len(A))] sum_right[-1] = A[-1] for i in range(1, len(A)): sum_left[i] = A[i] + sum_left[i-1] for i in range(len(A)-2, -1, -1): sum_right[i] = A[i] + sum_right[i+1] required_sum = temp / 3 index1 = 0 index2 = len(A) - 1 while index1 < index2: while index1 < index2 and sum_left[index1] != required_sum: index1 += 1 while index2 > index1 and sum_right[index2] != required_sum: index2 -= 1 return index1 < index2 and index1 != index2 ob1 = Solution() print(ob1.canThreePartsEqualSum([0,2,2,-6,6,-7,9,2,2,0,2]))
입력
[0,2,1,-6,6,-7,9,1,2,0,1]
출력
true
정리
이 알고리즘은 누적합 배열을 미리 계산해 두고 양쪽 끝에서부터 목표 합에 해당하는 지점을 찾아가는 방식입니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, 배열을 세 부분으로 나눌 수 있는지 빠르게 판단할 수 있습니다. 음수가 포함된 배열에서도 정확하게 동작한다는 점이 특징입니다.