JavaScript 배열에서 선형 시간 O(n)으로 첫 번째 중복 숫자 찾기

이번 문제에서는 1부터 n 사이의 정수로만 구성된, 길이가 n + 1인 읽기 전용(read-only) 배열을 입력으로 받는 JavaScript 함수를 작성해야 합니다.

함수는 반드시 선형 시간 O(n) 안에 실행되어야 하며, 추가로 사용하는 공간 역시 최대 O(n)을 넘지 않아야 합니다. 이 조건을 만족하면서 배열 안에서 한 번 이상 등장하는 숫자, 즉 중복 숫자를 하나 찾아 반환하면 됩니다.

문제 예시

예를 들어 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [3, 4, 1, 4, 1];

이 배열에는 4와 1이 각각 두 번씩 등장하므로 두 값 모두 정답 후보가 될 수 있습니다. 따라서 출력은 다음 중 하나여야 합니다.

const output = 4; // 또는 1

정답이 여러 개 존재할 경우 그중 어떤 값을 반환해도 무방합니다. 반대로 중복된 숫자가 전혀 없다면 -1을 반환해야 합니다.

접근 방법: Set(집합) 활용하기

가장 직관적이고 효율적인 방법은 Set 자료구조를 활용하는 것입니다. 배열의 요소를 처음부터 끝까지 순회하면서 각 요소를 Set에 하나씩 추가하고, 이미 Set에 존재하는 요소를 만나는 즉시 해당 값을 반환합니다.

• 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
• 공간 복잡도: O(n) — 최악의 경우 모든 요소를 Set에 저장하게 됩니다.

Set의 조회(has)와 삽입(add) 연산은 평균적으로 상수 시간에 처리되므로, 전체 알고리즘이 선형 시간 제약을 충족합니다.

예제 코드

const arr = [3, 4, 1, 4, 1];

const findRepeatedNumber = (arr = []) => {
   const set = new Set();
   for (const item of arr) {
      // 이미 Set에 존재한다면 처음으로 확인된 중복 숫자
      if (set.has(item)) {
         return item;
      }
      set.add(item);
   }
   // 중복이 존재하지 않는 경우
   return -1;
};

console.log(findRepeatedNumber(arr));

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

4

동작 원리 단계별 살펴보기

1. 3은 Set에 없으므로 추가합니다. → {3}
2. 4는 Set에 없으므로 추가합니다. → {3, 4}
3. 1은 Set에 없으므로 추가합니다. → {3, 4, 1}
4. 4는 이미 Set에 존재하므로 즉시 4를 반환하고 함수가 종료됩니다.

한 가지 유의할 점은, 이 방식이 "값의 크기가 가장 작은 중복"이 아니라 순회 도중 가장 먼저 중복으로 판별되는 숫자를 반환한다는 것입니다. 위 예제에서 1이 아니라 4가 먼저 반환되는 이유가 바로 이 때문입니다. 문제 조건상 어떤 중복 값을 반환해도 허용되므로, 이러한 동작 방식은 유효한 해답이 됩니다.