[Codility] Lesson 3.3 - TapeEquilibrium

2개 이상의(2 ~ 100000) 비어 있지 않은 정수(-1000 ~ 1000) 배열 A가 있다고 할 때, 특정 정수 P로 배열을 둘로 나누어 두 배열의 합의 차이를 구한 값 중 가장 작은 값을 구하는 함수를 작성한다.
예를 들어

A = {3,1,2,4,3} 일 때,

P=1, 차이=|3-10|=7
P=2, 차이=|4-9|=5
P=3, 차이=|6-7|=1
P=4, 차이=|10-3|=3

가장 작은 차이는 1

첫번째 풀이

무식하게 배열을 특정 인덱스로 나눠 두 개의 배열로 만든 후에 stream으로 sum을 구해서 두 sum의 차의 절대값을 구하려고 했다.

public int solution(int[] A) {
    int minimalDifference = -1;

    int firstSum = 0;
    int secondSum = 0;

    for (int i=1; i<A.length; i++) {
        int[] a = Arrays.copyOfRange(A, 0, i);
        int[] b = Arrays.copyOfRange(A, i, A.length+1);
        int tempMinimal = Math.abs(Arrays.stream(a).sum() - Arrays.stream(b).sum());

        if (minimalDifference < 0) {
            minimalDifference = tempMinimal;
            continue;
        }
        if (tempMinimal < minimalDifference) {
            minimalDifference = tempMinimal;
        }
    }

    return minimalDifference;
}

예상했지만 O(n*n) 시간 복잡도였고 Timeout으로 performance 측정에서 탈락.

두번째 풀이

전체 합을 구하고 왼쪽, 오른쪽 배열의 합으로 나누는 것으로 가정할 때 오른쪽 합은 전체 합 - 왼쪽 합으로 구하고 왼쪽 합은 전체 배열의 for문으로 하나씩 쌓도록 했다.
두 배열 합의 차이를 배열에 넣고 마지막에 배열의 최솟값을 리턴하는 것으로 수정

public int solution(int[] A) {
    List<Integer> diffSet = new ArrayList<>();

    int sum = Arrays.stream(A).sum();

    int leftSum = 0;
    int rightSum = 0;

    for (int i = 1; i < A.length; i++) {
        leftSum += A[i - 1];
        rightSum = sum - leftSum;
        diffSet.add(Math.abs(leftSum - rightSum));
    }

    return Collections.min(diffSet);
}

100% 통과 완료