[분석] Codility - TapeEquilibrium - Javascript

Codility 연습문제 > TapeEquilibrium > Javascript
| (A [0] + … + A [P-1])-(A [P] + … + A [N-1]) | 두 그룹의 절대값중 최소값을 구하는 문제.

실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.

[문제 및 조건]

N 개의 정수로 구성된 비어있지 않은 배열 A가 제공됩니다. 배열 A는 테이프의 숫자를 나타냅니다. 정수 P는 이 테이프를 비어 있지 않은 두 부분으로 분할합니다. ex) A[0], A[1], …, A[P − 1] 및 A[P], A[ P + 1], …, A[N-1] 쉽게 말하면 index 와 index + 1 사이를 분할하여 두 그룹으로 만들고, 왼쪽의 그룹의 합에서 오른쪽 그룹의 합을 뺀 절다 값 중에 가장 작은 수를 반환하는 문제입니다.

1. 비어있지 않은 배열이 주어진다.
2. index, index + 1 사이를 분할하여 그룹을 만들 수 있다.
3. 배열을 분할하고 왼쪽합 - 오른쪽합 의 절대값이 가장 작은수를 반환한다.
4. 예를들면, A = [3, 1, 2, 4, 3] 이면 위치값 3일 경우 (3 + 1 + 2) - (4 + 3) = 1 로 가장 작은 값이다.
   
   

[분석]

1. 배열의 길이는 2 ~ 100,000 범위의 정수이다.
2. 배열 각 요소는 -1,000 ~ 1,000 범위의 정수이다.
3. 가작 작은 분할은 2로 양쪽에 각각 하나씩만 존재하므로 가장 빠르게 계산할 수 있다.
4. 절대값을 사용하기위해 Math.abs() 함수를 이용하자.
   
   

[풀이]

1. 비어있지 않은 배열을 반복문으로 순환하면서 두 그룹으로 나누고 연산한다.
2. 두 그룹으로 배열의 합을 구하려면 reduce 함수를 사용해야 하고, 배열의 길이가 길수록 복잡도가 올라간다.
3. 먼저 전체 합을 구하고, 전체 합에서 순차적으로 빼나가는 것을 고려해보자.
4. 결과값뿐만 아니라 성능을 측정하는 문제로, 불필요한 2중 반복문을 피해야 합니다.

function solution(A) {
  let min = null;
  // 최초 한번 전체 합을 구할 필요가 있다.
  // 연산 범위의 최소 최대값을 배열로 구현한다.
  let range = [0, A.reduce((ac, cu) => ac + cu, 0)];  // [0, Max];

  for (let i = 0; i < A.length; i++) {
    const current = A[i];
    const prev = sums[0] + current; // 현재 숫자는 이전 전체값에 더해진다.
    const next = sums[1] - current; // 현재 숫자는 다음 전체값에서 뺀다.
    // Math.abs() 함수를 이용해 절대값을 구한다.
    const result = Math.abs(prev - next);

    // range[0], range[1]로 할당하는 것 보다 새로 정의하는게 효과적이다.
    range = [prev, next];

    // min 초기값이 null 인 경우 또는 절대값보다 크다면
    if (min === null || min > result) {
      min = result;
    }
  }

  return min;
}

[마치며]

TapeEquilibrium 문제는 반복 문안에 또 다른 반복문이나 유사 반복문 처리가 들어갈 경우 성능 문제를 일으킬 수 있습니다. 값을 구하기 위해 단순하게 생각하면 두 그룹의 합을 구하기 위해 reduce 또는 for 반복문을 사용해야하는 문제로 보일 수 있으나, 전체 합이 변함없고, 숫자가 하나씩 좌측으로 이동힌다는 점을 고려한다면 최대한 반복문을 하나만 사용해 순차적으로 분할해 왼쪽과 오른쪽 값의 차의 절댓값이 가장 작은 값을 찾아 반환하는 게 문제의 핵심인 것 같습니다. 전에도 얘기했지만 반복문을 2중 3중 사용하는 것은 시간 복잡도를 상승시키고 성능에 영행을 주기 때문에 어떻게 하면 반복문을 최소화하면서 원하는 값을 얻을 수 있을지 항상 고민하고 문제에 접근해야 합니다.