처음 n개의 자연수가 담긴 숫자 배열이 있다고 가정해 봅시다. 그런데 이 배열에는 한 요소가 두 번 등장하기 때문에 전체 요소 개수는 n+1개입니다. 우리의 목표는 배열을 입력받아 두 번 나타나는 숫자를 선형 시간(O(n)) 안에 찾아 반환하는 함수를 작성하는 것입니다.
방법 1: Array.prototype.reduce() 활용하기
다소 까다로워 보이는 접근 방식이지만, 코드가 가장 간결하다는 큰 장점이 있습니다. 먼저 코드부터 살펴보겠습니다.
const arr = [1,4,8,5,6,7,9,2,3,7];
const duplicate = a => a.reduce((acc, val, ind) => val + acc - (ind + 1)) + a.length - 1;
console.log(duplicate(arr));여기서 사용한 reduce 함수의 콜백은 배열의 각 요소에 대해 한 번씩 실행되며, 세 개의 인자를 받습니다.
- acc → 누산기(accumulator): 이전 반복에서 반환된 값
- val → 현재 처리 중인 요소의 값
- ind → 현재 요소의 인덱스
동작 원리 단계별 분석
이번에는 다음 배열에 같은 코드를 적용해 보겠습니다.
[ 2, 3, 1, 2]배열의 길이가 4이므로 콜백 함수는 원래 4번 실행되어야 하지만, reduce()에 initialValue 인자를 전달하지 않았기 때문에 반복은 인덱스 1부터 시작되고 누산기에는 인덱스 0의 값이 초기값으로 할당됩니다. 따라서 콜백은 총 3번 실행됩니다.
첫 번째 반복
acc = 2, val = 3, ind = 1
반환값 = 2 + 3 - (1 + 1) = 3두 번째 반복
acc = 3, val = 1, ind = 2
반환값 = 3 + 1 - (2 + 1) = 1세 번째 반복
acc = 1, val = 2, ind = 3
반환값 = 1 + 2 - (3 + 1) = -1배열 순회 종료
결국 reduce는 -1을 반환하고, 이어서 최종 계산이 수행됩니다.
-1 + (4 - 1) = -1 + 3 = 2따라서 duplicate() 함수는 2를 반환하며, 이는 실제 중복값과 정확히 일치합니다.
방법 2: Array.prototype.forEach() 활용하기
이 방법은 배열을 순회하며 모든 요소의 합을 구한 후, 첫 (n-1)개 자연수의 합을 빼는 원리를 이용합니다. 여기서 n은 배열의 길이입니다. 빼고 남은 값이 곧 두 번 등장한 숫자이므로, 그 값을 그대로 반환합니다.
예제 코드
const arr = [1,4,8,5,6,7,9,2,3,7];
const duplicate = a => {
let sum = 0;
const { length: n } = a;
a.forEach(num => sum += num);
return sum - ((n * (n - 1)) / 2);
}
console.log(duplicate(arr));출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
7마무리
두 방법 모두 배열을 한 번만 순회하므로 시간 복잡도 O(n)으로 선형 시간 안에 중복 요소를 찾을 수 있습니다. 코드의 간결함을 우선한다면 reduce() 방식을, 직관적인 수학적 접근과 가독성을 우선한다면 forEach() 방식을 선택하는 것이 좋습니다.