TapeEquilibrium_codility

문제

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

 

풀이

function solution(A) {
    if (A.length === 2) return Math.abs(A[0]-A[1]);
    let totalSum = A.reduce((cur, sum) => cur+sum, 0);
    let result = [];
    let rightSum = 0;
    for (let i = 0; i < A.length; i++) {
        rightSum += A[i];
        totalSum -= A[i];
        result.push(Math.abs(totalSum-rightSum));
    }

    return result.sort((a, b) => a - b)[0];
}

첫번째로 제출한 답변이다.

배열 인덱스 i일때 합과 배열요소의 총합에서 인덱스 i요소의 값을 뺀 나머지를 배열에 담는다.

담겨진 배열을 오름차순으로 하여 가장 작은 값을 리턴하도록 로직을 작성했다. 

문제는 [-10, -20, -30, -40, 100]인 경우 결과 값이 20으로 나와야되는데 0으로 나오는 이슈가 있었다.

 

function solution(A) {
    const N = A.length;
    const totalSum = A.reduce((a, b) => a + b);
    let rightSum = A[0];
    let leftSum = totalSum - A[0];
    let minDiff = Number.MAX_SAFE_INTEGER;
    let diff;

    for(let P=1; P<N; P++){
        diff = Math.abs(leftSum - rightSum);
        if(diff < minDiff){
            minDiff = diff;
        }
        rightSum += A[P];
        leftSum -= A[P];
    }

    return minDiff;
}

변수 rightSum의 초기값을 0이 아닌 A배열의 첫번째값으로 설정하였고, 변수 leftSum을 새로 추가했다.

P가 1일때

leftSum = -10 -10 = -20

rightSum = 10 -10 = 0

Math.abs(-20 -0) = 20을 얻을 수 있는 로직이다.