문제 상황
1부터 n까지의 숫자가 포함된 배열을 입력받아, 이 배열 속에서 빠진 숫자 하나를 찾아 반환하는 JavaScript 함수를 작성해야 합니다.
여기서 까다로운 점은 두 가지입니다. 첫째, 배열에서 정확히 한 개의 숫자가 누락되어 있고, 둘째, 배열이 정렬되어 있지 않다는 것입니다. 다행히도 반복문으로 일일이 비교하지 않고도 수학적 공식을 활용하면 매우 효율적으로 문제를 해결할 수 있습니다.
해결 아이디어: 가우스 덧셈 공식
핵심 원리는 간단합니다. 1부터 m까지의 연속된 자연수의 합은 m × (m + 1) ÷ 2라는 가우스 덧셈 공식으로 구할 수 있습니다.
누락된 숫자가 하나뿐이라면, 전체 범위(1부터 마지막 숫자까지)의 이론적인 합에서 실제 배열 요소들의 합을 빼면 그 차이가 곧 누락된 숫자가 됩니다. 이 방법은 배열을 정렬할 필요도 없고, 시간 복잡도 O(n)으로 단 한 번의 순회만으로 답을 구할 수 있습니다.
구현 예제
다음은 reduce() 메서드와 가우스 공식을 활용한 코드입니다.
const arr = [4, 7, 1, 8, 9, 5, 2, 3];
const findMissing = (arr = []) => {
// 배열 요소들의 실제 합계를 구합니다.
const sumArr = arr.reduce((acc, val) => acc + val);
const { length: len } = arr;
// 누락된 숫자가 없다고 가정했을 때의 이론상 총합 (1부터 len+1까지)
const sumFirst = (len + 1) * (len + 2) * .5;
// 두 값의 차이가 바로 누락된 숫자입니다.
const missing = sumFirst - sumArr;
return missing;
};
console.log(findMissing(arr));코드 동작 원리
배열 [4, 7, 1, 8, 9, 5, 2, 3]은 길이가 8이며, 1부터 9까지의 숫자 중 6이 빠져 있습니다. 코드가 동작하는 과정을 살펴보겠습니다.
먼저 reduce()를 사용해 배열 요소의 실제 합(39)을 구합니다. 다음으로 배열 길이(len)가 8이므로, 완전한 시퀀스라면 1부터 9까지의 합인 (9 × 10 × 0.5) = 45가 되어야 합니다. 두 값을 빼면 45 − 39 = 6이 되고, 이것이 정확히 누락된 숫자입니다.
출력 결과
6
마무리
이 접근 방식은 배열을 정렬하거나 추가 자료구조를 사용하지 않고도 선형 시간 안에 누락된 숫자를 찾을 수 있는 가장 간결하고 효율적인 방법입니다. 다만 배열의 크기가 매우 커서 합계가 Number.MAX_SAFE_INTEGER를 초과할 가능성이 있다면, XOR 비트 연산을 활용한 대안을 고려하는 것이 좋습니다.