TapeEquilibrium

/Codility

문제 해석

요약

주어진 배열을 두 부분으로 나누어 각각 부분합을 구한다. 두 부분합의 가장 작은 차이(절대값)을 구하시오.

전문

🇰🇷 번역

N개의 정수로 구성된 비어있지 않은 배열 A가 주어진다. 배열 A는 테이프의 위의 숫자를 나타난다.

0<P<N 처럼 정수 P는 이 테이프를 비어있지 않은 두 부분으로 나눈다: A[0], A[1], ..., A[P − 1] 와 A[P], A[P + 1], ..., A[N − 1].

두 부분의 다른 점은 다음의 값이다: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

다시 말해서, 첫부분과 두번째 부분의 합 사이의 절대값 차이이다.

배열 A가 다음과 같다면:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

이 테이프를 4가지로 분리할 수 있다:

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

함수를 작성하시오:
function solution(A);

N개의 정수로 구성된 비어있지 않은 배열 A가 주어지고, 가능한 최소 값을 반환하시오.

다음이 주어진다면:

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

위의 설명에 따르면 함수는 1을 반환해야한다.

다음과 같은 가정에 따라 효율적인 알고리즘을 작성하시오:

  • N은 [2..100,000]범위 안의 정수이다;
  • A의 각 요소는 [−1,000..1,000]범위 안의 정수이다.

🇺🇸 원문

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:

function solution(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].

🤔 문제 해결 방법 구상

두 부분으로 나누어 합을 비교하는 문제이므로 전체합을 이용하는 것이 좋을 것 같다.

  1. 주어진 배열의 총 합을 구한다.
  2. 왼쪽부터 개수를 늘려가며 그 부분합을 구한다.

    • for loop의 범위를 잘 생각해야한다.
  3. 두 부분의 합을 뺀 절대값을 구한다.

    • 첫번째 부분: 2번의 부분합
    • 두번째 부분: 전체 총합 - 부분합
    • 절대값 계산: 부분합 - (전체 - 부분합) = 2 * 부분합 - 전체
    • 절대값은 Math.abs메소드를 사용하면 쉽게 구할 수 있다.
    • 기존의 절대값보다 더 작을때만 저장한다.
  4. 부분의 합이 다 끝나면, 저장된 최소 절대값을 리턴한다.

코드 구현

function solution(A) {
  const total = A.reduce((acc, cur) => acc + cur);
  let partSum = A[0];
  let minDiff = Math.abs(2 * partSum - total);
  for (let i = 1; i < A.length - 1; i++) {
    partSum += A[i];
    let diff = Math.abs(2 * partSum - total);
    if (minDiff > diff) {
      minDiff = diff;
    }
  }

  return minDiff;
};

결과 분석

Task Score: 84%
Correctness: 71%
Performance: 100%

시간 복잡도는 O(n). 공간 복잡도는 O(n)으로 예상한다.

🧐 개선

정확도에서 점수가 낮게나왔다. 틀린 부분을 찾아보니, 요소가 두개일때 문제가 생기는 것이다! 띠용...

나름 코드를 신경쓴다고 for문을 인덱스 1부터 적용되게 했는데.... 이렇게 되면 요소가 2개일때 문제가 된다.

처음에 A의 길이가 2일 경우를 처리해주자.

개선 코드

function solution(A) {
  if (A.length === 2) return Math.abs(A[0] - A[1]);

  const total = A.reduce((acc, cur) => acc + cur);
  let partSum = A[0];
  let minDiff = Math.abs(2 * partSum - total);
  for (let i = 1; i < A.length - 1; i++) {
    partSum += A[i];
    let diff = Math.abs(2 * partSum - total);
    if (minDiff > diff) {
      minDiff = diff;
    }
  }

  return minDiff;
}

개선 결과

Task Score: 100%
Correctness: 100%
Performance: 100%

마찬가지로 시간 복잡도는 O(n). 공간 복잡도는 O(1)으로 예상한다.
요소가 두개일 경우를 처리해주니 정확도와 성능 모두 100%가 나왔다.

마무리

loop을 사용할 땐, 범위를 다시 한 번 더 체크하자!

Reference & Learn More

MDN Math.abs

Tags
Comments