2018-11-17
[JS] Cyclic Rotation
EASY

개요

서로 다른 N개의 integer로 채워진 베열 A가 주어집니다. 배열 값은 1 ~ (N+1) 범위를 가집니다. 다시 말해, 정확히 하나의 요소의 값이 N+1로 변했습니다.

예시

배열 A가 [2, 3, 1, 5]로 주어진다면, 4를 반환해야 합니다. 1 ~ 4범위에서 4가 빠졌습니다.

문제

배열 A가 주어질 때, 빠진 값을 반환하세요.

제한

  • integer N은 0 ~ 100,000의 범위를 가집니다.
  • 배열 A의 모든 요소는 서로 다른 값을 가집니다.
  • 배열 A의 모든 요소는 1 ~ (N+1)의 범위를 가집니다.

풀이

스코어 100%

function solution(A) {
  const expected = (A.length + 1) * A.length / 2
  let actual = 0

  for (let i = 0; i < A.length; i++) {
    actual += A[i]
  }

  return A.length - (actual - expected - 1)
}

설명

1부터 N까지의 수 중에서 하나의 수가 N+1로 변했습니다.
배열을 정렬하고, 1부터 하나씩 빈 값을 찾아갈 수도 있지만, 딱 하나의 수가 N+1로 변한 데에 주목하세요.

만약, 하나의 수가 N+1로 변하지 않았다면, 1부터 N까지의 합은 배열 순회를 하지 않아도 가우스가 9세 때 발견한 덧셈법으로 알 수 있습니다:

  1. 가우스는 1 + 2 + ... + 99 + 100의 합을 구하기 위해, 식을 반으로 접어 101 * 50을 계산했습니다.
  2. 이를 수식으로 나타내면, (N+1)*N/2입니다.

하지만 배열 A는 임의의 수 하나가 N+1로 변했습니다. 임의의 수를 구하기 위한 식은 간단한 치환으로 다음과 같이 구할 수 있습니다.

  • N+1로 바뀌기 전의 값 === N - (actual - expected - 1)