LeetCode | Easy | 1013. Partition Array Into Three Parts With Equal Sum

Jun 20, 2024

Published byJynn

999

LeetCode | Easy | 1013. Partition Array Into Three Parts With Equal Sum

Problems

📘 Src: LeetCode
🗂️ Cat: Greedy

Description

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])

Constraints

3 <= arr.length <= 5 * 10^4
-10^4 <= arr[i] <= 10^4

Examples

arr	Output
[0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]	true
[0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1]	false
[3, 3, 6, 5, -2, 2, 5, 1, -9, 4]	true

Solutions

⏳ TC: O(n)
💾 SC: O(1)

Solution.java

import java.util.*;

class Solution {

    public boolean canThreePartsEqualSum(int[] arr) {
        int totalSum = Arrays.stream(arr).sum();
        
        // 전체 합이 3으로 나누어지지 않으면 불가능
        if (totalSum % 3 != 0) {
            return false;
        }
        
        int target = totalSum / 3;
        int partSum = 0;
        int count = 0;

        // 배열을 순회하면서 부분 합 계산
        for (int num : arr) {
            partSum += num;
            
            // 부분 합이 목표 합과 일치하면 카운트 증가 및 부분 합 초기화
            if (partSum == target) {
                count++;
                partSum = 0;
            }
        }
        
        // 목표 합을 가진 부분 합이 세 번 이상 발생해야 true 반환
        return count >= 3;
    }
}

Approaches

이 문제는 주어진 배열을 세 부분으로 나누어 각각의 부분이 동일한 합을 가지도록 하는 문제입니다. 여기서 핵심은 각 부분의 합이 동일해야 하기 때문에 전체 배열의 합이 3으로 나누어져야 한다는 점입니다. 전체 합이 3으로 나누어지지 않으면 세 부분으로 나누는 것이 불가능합니다. 또한, 세 번째 목표 합에 도달한 시점에서 배열의 나머지 부분이 반드시 세 번째 부분 합을 충족하게 되어 있기 때문에, 목표 합에 도달한 횟수가 3번 이상인 경우 true를 반환할 수 있습니다. 이는 전체 합이 3의 배수이기 때문에 가능한 것입니다. 따라서 네 번 이상의 목표 합이 발생하더라도 이는 이미 문제의 요구 사항을 충족합니다.

이를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

전체 합 계산: 배열의 모든 요소를 더하여 전체 합을 구합니다. 이 값이 3으로 나누어지는지 확인하는 것이 첫 번째 단계입니다.
전체 합의 3 배수 여부 확인: 전체 합이 3으로 나누어지지 않으면 세 부분으로 나누는 것이 불가능하므로 false를 반환합니다. 이는 세 부분의 합이 동일해야 하므로 전체 합이 3의 배수가 아니면 불가능하기 때문입니다.
부분 합 목표 설정: 전체 합을 3으로 나누어 각 부분이 가져야 할 목표 합을 구합니다. 예를 들어, 전체 합이 9라면 각 부분의 합은 3이 되어야 합니다.
부분 합 계산: 배열을 순회하면서 부분 합을 계산하고, 부분 합이 목표 합과 일치할 때마다 카운트를 증가시킵니다. 이 과정에서 부분 합이 목표 합에 도달하면 현재까지의 부분 합을 초기화하여 다음 부분 합을 계산합니다.
결과 반환: 목표 합에 도달한 부분이 세 번 이상 발생하면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 예를 들어, 배열 [0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1]은 0 + 2 + 1, -6 + 6 - 7 + 9 + 1, 2 + 0 + 1 세 부분으로 나누어질 수 있어 true를 반환합니다.

이 알고리즘은 배열을 한 번 순회하면서 각 요소를 처리하므로 시간 복잡도는 O(n)이며, 추가적인 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.

Attempts

처음에는 이중 루프를 사용하여 배열을 순회하면서 가능한 모든 부분 합을 계산하는 방식으로 접근했습니다. 이는 배열의 각 부분을 일일이 계산하여 조건을 만족하는지 확인하는 방식으로 작성하면서도 시간 제한에 걸리겠다는 느낌이 들었습니다. 전체 합이 3으로 나누어져야 한다는 중요한 원리를 떠올리지 못했기 때문에 비효율적으로라도 각 부분 합을 계산하는데 집중했습니다. 이를 구현한 코드는 아래와 같습니다:

Solution.java

import java.util.*;

class Solution {

    public boolean canThreePartsEqualSum(int[] arr) {
        for (int i = 0; i < arr.length - 2; i++) {
            for (int j = i + 1; j < arr.length - 1; j++) {
                int sum = sum(arr, 0, i);
                if (sum == sum(arr, i + 1, j) && sum == sum(arr, j + 1, arr.length - 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    private int sum(int[] arr, int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += arr[i];
        }
        return sum;
    }
}

이 접근 방식은 각 가능한 부분 합을 일일이 계산해야 하므로 비효율적이며, 시간 복잡도가 O(n^2)로 매우 높습니다. 따라서 정확한 답을 도출하기는 하지만, 배열의 길이가 길어질수록 실행 시간이 급격히 증가하여 시간 제한에 걸릴 수 있습니다.

최적화된 알고리즘은 배열을 한 번만 순회하면서 부분 합을 계산하고 목표 합에 도달할 때마다 카운트를 증가시켜 효율적으로 문제를 해결합니다.

Algorithm
Greedy