[Codility Lessons] Tape Equilibrium

숫자 배열에서 P를 기준으로 배열을 나누고 각 나뉜 부분의 합의 가장 작은 차이를 리턴하는 함수를 작성하는 문제입니다.

예를 들어,
[3, 1, 2, 4, 3] 다음과 같은 배열에서 P의 인덱스가 1이라고 할 때,
배열은 [3] [1, 2, 4, 3]으로 나뉩니다.
각 배열의 합은 3과 10으로, 두 합의 차이는 7입니다.

[3], [1, 2, 4, 3] -> 3:10 -> 7
[3, 1] [2, 4, 3] -> 4:9 -> 5
[3, 1, 2] [4, 3] -> 6:7 -> 1
[3, 1, 2, 4] [3] -> 10:3 -> 7

따라서 가장 작은 차이는 1이 됩니다.

function solution(A) {
  // 
  let min = 2000;
  for (let i = 1; i < A.length; i++) {
    const head = A.slice(0, i).reduce((acc, cur) => acc + cur);
    const tail = A.slice(i).reduce((acc, cur) => acc + cur);
    if (min > Math.abs(head - tail)) {
      min = Math.abs(head - tail);
    }
  }
  return min;
}

채점 결과 퍼포먼스 테스트에서 모두 타임 에러가 발생했습니다.
시간복잡도는 O(N*N)입니다.

다른 풀이를 참고하여 전체 합에서 구하는 방식으로 다시 풀었습니다.

function solution(A) {
  let min = 2000;
  const arrSum = A.reduce((acc, cur) => acc + cur);
  let leftSum = A[0];
  let rightSum = arrSum - A[0];
  for (let i = 1; i < A.length; i++) {
    if (Math.abs(leftSum - rightSum) < min) {
      min = Math.abs(leftSum - rightSum);
    }
    leftSum += A[i];
    rightSum -= A[i];
  }
  return min;
}