Leetcode 1013. Partition Array Into Three Parts With Equal Sum

Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

 

정수 배열 arr이 주어졌을 때 비지 않는 3개의 배열 나눈 부분들의 합이 같을 시 참을 반환하라. 공식적으로 인덱스 i + 1 < j로 (arr[0] + arr[1] + ... + ar[i] == ar[i + 1] + ar[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length]을 찾을 수 있는 경우 배열을 분할할 수 있다.

 

Example 1:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]

Output: true

Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

 

Example 2:

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]

Output: false

 

Example 3:

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]

Output: true

Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

 

Constraints:

• 3 <= arr.length <= 5 * 104
• -104 <= arr[i] <= 104

 

처음 이 문제를 읽고 나는 동적 프로그래밍 혹은 역추적 방법들을 노렸다 하지만 이 방법들로 풀기엔 너무 복잡했다. 왜냐하면 일단 동적 프로그래밍으로 쉬운 입력 값을 예시 삼아 아래와 같은 과정을 그렸다.

 

arr = [1,2,3,4]

 

 

              [1,         2,                 3,          4]

             /             |                   |            \

           /               |                   |              \

[1 + 2, 3, 4]     [2 + 1, 3, 4]    [3 + 1, 2, 4]  [4 + 1, 2, 3]

[1 + 3, 2, 4]     [2 + 3, 1, 4]    [3 + 2, 1, 4]  [4 + 2, 1, 3]

[1 + 4, 2, 3]     [2 + 4, 1, 3]    [3 + 4, 1, 2]  [4 + 3, 1, 2]

 

나는 사실 동적 프로그래밍에 익숙하지 않아서 도저히 어떻게 풀지는 몰랐다. 들어본 역추적도 생각해봤지만 막막했다.

그래서 유튜브를 켰더니 이럴 수가! O(N)에 풀 수 있는 기적을 보았다.

 

너무 쉬운 알고리즘이지만 솔직히 직감적이지 않았다. 왜냐하면 만약 첫 예제를 실행하면 안 되는 문제는 내가 문제를 소홀히

문제에서 arr[0] + ... + a[i] == a[i + 1] + ... + [j - 1] == a[j] + ... + a[arr.length - 1]이라고 명시되어있기 때문이다.

그 말은 입력 자체가 반드시 [0 + ... +  i], [i+1 + ... +  j-1], [j + ... + arr.length -1] 이렇게 나눌 수 있다는 것이다.

나는 덧셈을 자유롭게 arr[i]과 arr[arr.length - 1] 사이의 숫자들로 덧셈을 쓸 줄 알았다, 위에 동적 프로그래밍 과정처럼 다양하게 말이다.

 

 

성공 코드

class Solution {
    public boolean canThreePartsEqualSum(int[] arr) {
        int sum = 0;
        
        for (int num : arr) {
            sum += num;
        }
        
        if (sum % 3 != 0) {
            return false;
        }
        
        int average = sum / 3;
        int partitionCount = 0;
        int currentPartitionSum = 0;
        
        for (int num : arr) {
            currentPartitionSum += num;
            
            if (currentPartitionSum == average) {
                currentPartitionSum = 0;
                partitionCount++;    
            }
        }
 
        return (partitionCount > 2) ? true : false; // there are at least three arrays
    }
}

N = arr 배열 크기

시간 복잡도: O(N)

공간 복잡도: O(1)

 

 

코드는 간단하다.

 

if (sum % 3 != 0)

먼저 배열의 총합을 구하고 나머지 값을 구하는 modulus(%) 연산자로,

총합 % 3 계산 후 나머지 값이 0이 아니면 거짓을 반환한다.

이유는 삼등분 합이 모두 동일하고 총합과 일치하려면 나머지는 없어야 한다.

예: 11 % 3 = 1      1이 남으므로 11은 삼등분으로 나눌 수 없다.

예: 12 % 3 = 0      12를 4, 4, 4되며 12 - 12는 0이다.

 

이제 배열의 값들을 차례차례 더해 평균과 동일시 partitionCount를 1씩 더하고 

마지막 partitionCount이 2보다 높으면 참을 반환한다.

 

average = 배열 총합 평균.

partitionCount = 분할 카운트.

currentPartitionSum = 현재 분할의 합.

 

for (int num : arr) 문으로 각각 배열의 값들을 접근한다.

currentPartitionSum에 현재 값을 더한다.

 

if (currentPartitionSum == average) 만약 현재 분할의 값이 평균과 동일시

currentPartitionSum를 0으로 초기화시켜 다음 분할의 덧셈을 준비한다.

partitionCount에 1 더한것은 한 분할이 끝났음 나타내는 카운트이다.

 

마지막으로 partitionCount가 3개 이상일 경우 참 혹은 거짓을 반환한다.

 

 

왜 3이 아니고 3 이상이라 궁금해서 마지막 줄을 아래와 같이 바꿨다.

return (partitionCount == 3) ? true : false;

 

그러나 [0,0,0,0] 입력값에서 에러가 났다.