Lesson 3 - Tape_Equilibrium

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7
Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].

---

첫풀이

일단 문제에 있는 요구사항을 완벽하게 구현하려 노력하였다.
결과는 모두 정답이었지만 0(N) * 2O(N) 에 가까우므로 역시 퍼포먼스 테스트에서 모두 FAIL이 났다. 줄이려면 좌변과 우변의 합을 루프가 아니라 더 빠르게 구해야 한다는 것은 알고 있었다.

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
 
        int N = A.length;

        int[] resultArray = new int[N-1];
        int resultArrayIndex = 0;

        for(int P=1; P<N; P++) {
            int a = 0;
            int b = 0;

            for(int i=0; i<P; i++) {
                a += A[i];
            }

            for(int j=P; j <= (N-1); j++) {
                b += A[j];
            }

            int difference = getAbsoluteDifference(a, b);
           
            resultArray[resultArrayIndex] = difference;
            resultArrayIndex++;
        }

        Arrays.sort(resultArray);
        return resultArray[0];
    }

    private int getAbsoluteDifference(int a, int b) {
        int result = b-a;
        return result > 0 ? result : - result;
    }
}

베스트 답안

내가 고민한 부분을 쉽게 풀은 답안이다.

1. 배열의 합을 일단 전부 구놓는다.
2. 우변은 배열의 합 - 좌변으로 구한다.
3. 배열에 저장한다.

저장할 때 Math.abs로 절대 값을 구한다.

Collectio함수의 최소 값으로 바로 반환하였다.

문과 출신인 나로서는 1번, 2번의 경우 문제를 많이 풀어 머리를 수학적으로 바꾸려고 노력해야 겠다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
 public int solution(int[] A) {
        List sumList = new ArrayList();
 
        int left = 0;
        int right = 0;
        int sum = 0;
 
        for(int i : A)  sum += i;
 
        for(int j = 1 ; j < A.length ; j++){
            left += A[j-1];
            right = sum - left;
            sumList.add(Math.abs(left - right));
        }
 
        return (int)Collections.min(sumList);
    }
}