2018-11-17
[JS] Perm Missing Elem
EASY

개요

N개의 integer로 채워진 배열 A가 주어집니다. 배열 A는 대표 숫자가 있습니다.
0 < P < N을 만족하는 정수라면, P를 기준으로 배열 A를 두 조각 낼 수 있습니다:

  • A[0], A[1], ..., A[P-1] 그리고 A[P], A[P+1], ..., A[N-1]로 나눌 수 있어요.

나뉜 부분의 합의 차를 구할 수 있습니다.

예시

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
  • P = 1일 때, 차이는 |3 - 10| = 7입니다.
  • P = 2일 때, 차이는 |4 - 9| = 5입니다.
  • P = 3일 때, 차이는 |6 - 7| = 1입니다.
  • P = 4일 때, 차이는 |10 - 3| = 7입니다.

문제

두 조각 난 부분의 합의 차가 가장 작은 P를 구해주세요.

제한

  • 배열 A의 길이 N은 2 ~ 100,000의 범위를 갖는 정수입니다.
  • 배열 A의 각 요소는 -1000 ~ 1000의 범위를 갖는 정수입니다.

풀이

스코어 100%

function solution(A) {
  let sum = 0, difference = 0, first = 0, second = 0, min = 1000
  
  for (let i = 0; i<A.length; i++) {
    sum += A[i]
  }
  
  for (let p = 1; p<A.length; p++) {
    first += A[p-1]
    second = sum - first
    difference = Math.abs(first-second)

    if (min > difference) {
      min = difference
    }
  }

  return min
}

설명

두 부분의 합을 매번 계산할 필요가 없다는 점에 주목하세요.

  • 전체 배열의 합을 구한 뒤, 첫 번째 부분의 합을 빼면 두 번째 부분의 합을 알 수 있습니다.
  • 첫 번째 부분의 합도 매 번 계산할 필요 없이 반복문에서 한 번씩만 더하며 누산하면 됩니다.