문제 정의
길이가 n인 숫자 배열이 주어졌다고 가정해 보겠습니다. 이 배열에는 0부터 n까지의 모든 정수가 들어 있지만, 단 하나의 숫자가 누락되어 있습니다. 누락된 숫자는 어떤 값이든 가능하며, 배열은 정렬되어 있지 않습니다. 우리가 작성할 JavaScript 함수는 이 누락된 숫자를 찾아 반환해야 하며, 선형 시간(O(n))과 상수 공간(O(1))이라는 제약 조건 안에서 동작해야 합니다.
접근 방식: 등차수열 합 공식 활용
배열에 0부터 n까지의 숫자가 하나씩 들어 있고 그중 하나만 비어 있다는 점이 핵심 힌트입니다. 이 성질을 활용하면 다음과 같은 전략으로 문제를 해결할 수 있습니다.
- 배열 요소의 실제 합계를 구합니다. —
reduce()를 사용해 한 번의 순회로 계산할 수 있으며, 시간 복잡도는 O(n)입니다. - 완전한 배열일 때의 기대 합계를 가우스 덧셈 공식
n × (n + 1) / 2로 계산합니다. — 반복 없이 상수 시간(O(1))과 상수 공간으로 구할 수 있습니다. - 두 값의 차이가 바로 누락된 숫자입니다.
구현 예제
const arr = [3, 7, 8, 10, 11, 0, 2, 6, 1, 4, 5];
const findMissing = (arr = []) => {
// 1. 배열 요소의 실제 합계
const sum = arr.reduce((acc, val) => acc + val);
// 2. 0부터 n까지의 기대 합계 (가우스 공식)
const { length: num } = arr;
const expectedSum = (num * (num + 1)) / 2;
// 3. 차이가 곧 누락된 숫자
return expectedSum - sum;
};
console.log(findMissing(arr));
실행 결과
9
코드 설명
예제 배열의 길이는 11입니다. 즉, 원래라면 0부터 11까지 총 12개의 숫자가 있어야 하는데 하나가 빠진 상태입니다.
- 기대 합계: 11 × 12 ÷ 2 = 66
- 실제 합계: 3 + 7 + 8 + ⋯ + 4 + 5 = 57
- 누락된 숫자: 66 − 57 = 9
배열을 정렬하지 않고도 단 한 번의 순회와 몇 개의 변수만으로 답을 구했습니다. 따라서 이 알고리즘은 시간 복잡도 O(n), 공간 복잡도 O(1) 조건을 모두 만족합니다.
참고: XOR 연산을 이용한 대안
합계 대신 XOR(배타적 논리합) 연산을 사용하는 방법도 널리 알려져 있습니다. 같은 값을 두 번 XOR하면 0이 된다는 성질을 이용해, 인덱스와 배열 요소를 모두 차례로 XOR하면 최종적으로 누락된 숫자만 남게 됩니다. 이 방식은 C나 Java처럼 정수 오버플로우가 걱정되는 언어에서 특히 유용하지만, JavaScript의 Number는 매우 넓은 안전 정수 범위(Number.MAX_SAFE_INTEGER 약 9×10¹⁵)를 지원하므로 일반적인 경우에는 합계 방식만으로 충분합니다.