중복 검사 함수를 O(n²)에서 O(n)으로 바꾸기

배열에 중복된 값이 있는지 검사하는 함수를 짠다고 해보자. 가장 먼저 떠오르는 건 이중 루프다.

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

동작은 한다. 문제는 배열이 커질 때다.

이 코드는 왜 O(n²)인가

바깥 루프가 i = 0일 때 안쪽 루프는 n - 1번 돈다. i = 1일 때는 n - 2번, 그다음은 n - 3번. 이렇게 줄어들기 때문에 총 비교 횟수는 다음과 같다.

(n-1) + (n-2) + ... + 1 = n(n-1)/2

전개하면 n²/2 - n/2다. 안쪽 루프가 매번 n번씩 도는 게 아니니 정확히는 n²의 절반쯤이다. 그런데도 이 코드의 시간복잡도는 O(n²)라고 쓴다.

Big-O가 보는 건 정확한 연산 횟수가 아니라 n이 커질 때의 증가 추세이기 때문이다. 그래서 두 가지를 버린다. 상수 계수(1/2)와 낮은 차수 항(n/2)이다. n²/2든 n²이든 n이 2배가 되면 둘 다 4배가 되고, -n/2는 n이 커질수록 n²/2 앞에서 무의미해진다.

숫자로 보면 감이 온다. 항목이 1,000개면 약 50만 번 비교하고, 10,000개면 약 5,000만 번 비교한다. 데이터가 10배 늘었는데 작업량은 100배 늘었다.

첫 번째 시도, 그리고 함정

Set을 쓰면 O(n)이 되겠다는 생각으로 이렇게 고쳤다.

function hasDuplicate(arr) {
  const setArr = new Set(arr);

  return arr.some(value => setArr.has(value));
}

복잡도 계산 자체는 맞다. Set을 만드는 데 O(n), some으로 한 번 순회하면서 has를 O(1)에 부르니 전체가 O(n)이다.

그런데 [1, 2, 3]을 넣어보면 true가 나온다. 중복이 하나도 없는데도.

setArr은 arr을 통째로 넣어 만든 Set이다. 그러니 arr의 모든 원소는 정의상 이 Set 안에 있다. has는 언제나 true를 반환하고, 결국 이 함수는 입력이 무엇이든 true를 뱉는다. 복잡도는 줄였지만 기능이 사라진 코드였다.

원인을 짚어보면 Set의 역할을 잘못 잡은 것이다. Set은 "지금까지 본 값"을 기억하는 용도로 써야 하는데, 시작부터 전부 채워버리면 "이미 본 값"과 "아직 안 본 값"의 구분이 없어진다.

순회하면서 채우기

기억하는 용도로 쓰려면 Set을 미리 만드는 게 아니라 순회하면서 점진적으로 채워야 한다.

function hasDuplicate(arr) {
  const seen = new Set();

  for (const value of arr) {
    if (seen.has(value)) return true;
    seen.add(value);
  }

  return false;
}

핵심은 순서다. 확인이 먼저, 추가가 나중이다. 값을 넣기 전에 이미 있는지 물어봐야 중복을 잡아낼 수 있다. 순서를 뒤집으면 방금 넣은 자기 자신을 발견하고 항상 true가 된다.

여기서 두 가지를 놓치기 쉽다.

하나는 new다. const seen = Set()처럼 new 없이 호출하면 TypeError: Constructor Set requires 'new'가 난다. Set은 클래스라서 생성자 호출이 필요하다.

다른 하나는 마지막 return false다. 이게 없으면 중복이 없을 때 함수가 undefined를 반환한다. if (hasDuplicate(arr))처럼 쓰면 undefined도 falsy라 우연히 동작하지만, hasDuplicate라는 이름은 boolean을 약속하고 있다. 반환 타입이 상황에 따라 달라지는 함수는 호출부에서 === false 같은 비교를 하는 순간 조용히 깨진다.

Set.has는 왜 O(1)인가

이 리팩터링이 성립하는 근거는 Set.has가 O(1)이라는 데 있다. 이 전제가 무너지면 아무 의미가 없다. 실제로 Set 대신 배열로 같은 구조를 짜면 다시 O(n²)로 돌아간다.

// 구조는 같지만 여전히 O(n²)
function hasDuplicate(arr) {
  const seen = [];

  for (const value of arr) {
    if (seen.includes(value)) return true;
    seen.push(value);
  }

  return false;
}

includes는 배열을 처음부터 하나씩 비교하므로 O(n)이다. 그게 n번 반복되니 결국 O(n²)다. 루프가 하나뿐이어도 안에서 O(n)짜리를 부르면 이중 루프와 다르지 않다.

Set은 해시 테이블 기반이라 값 자체로부터 저장 위치를 계산한다. 그래서 원소가 몇 개든 조회 비용이 거의 일정하다. 엄밀히는 해시 충돌이 심하면 나빠질 수 있어 평균 O(1)이라고 말한다.

공짜는 아니다. 이중 루프 버전은 추가 메모리를 거의 쓰지 않았지만, Set 버전은 원소 n개를 담을 공간을 따로 쓴다. 시간을 줄이는 대신 공간을 내준 것이고, 자료구조 선택은 대체로 이런 교환이다.

프론트엔드 코드에서 자주 만나는 복잡도

특히 마지막 줄이 실무에서 조용히 생긴다. 겉보기엔 루프가 하나인데 실제로는 이중 루프인 코드가 있다.

// 겉보기엔 순회 한 번, 실제로는 O(n × m)
const selected = items.filter(item => selectedIds.includes(item.id));

items를 한 번 순회하는 동안 매번 selectedIds 전체를 훑는다. 두 배열이 각각 1,000개면 100만 번 비교다. 조회할 쪽을 Set으로 바꾸면 O(n + m)이 된다.

const selectedIdSet = new Set(selectedIds);
const selected = items.filter(item => selectedIdSet.has(item.id));

여기서는 Set을 미리 통째로 만드는 게 맞다. 앞선 함정과 반대되는 것 같지만, 목적이 다르다. 이 경우 Set은 "검사 대상"이 아니라 **"검사 기준이 되는 별개의 집합"**이다. 자기 자신을 담은 Set으로 자기 자신을 검사할 때만 문제가 됐던 것이다.

그래서 항상 O(n)이 옳은가

그렇지는 않다. n이 작으면 이중 루프가 더 빠를 수도 있다. Set은 객체를 만드는 비용과 값마다 해시를 계산하는 비용이 있고, 이중 루프는 중복을 만나는 즉시 빠져나온다. 배열 길이가 열 개 안팎이고 앞쪽에서 중복이 나온다면 이중 루프가 이긴다.

Big-O는 어디까지나 n이 충분히 커질 때의 이야기다. 상수를 버린다는 규칙은 뒤집어 보면 n이 작을 때는 그 상수가 결과를 지배할 수도 있다는 뜻이기도 하다.

판단 기준은 n이 커질 가능성이 있는지다. 서버에서 받아온 목록, 사용자가 계속 추가하는 항목, 화면에 렌더링할 리스트처럼 크기를 통제할 수 없는 데이터라면 처음부터 O(n)으로 짜두는 편이 안전하다. 반대로 길이가 고정된 상수 배열이라면 굳이 바꿀 이유가 없다.

마무리

이번 리팩터링에서 얻은 건 결국 하나다. O(1)에 조회할 수 있는 자료구조를 곁에 두면, 반복 탐색을 없앨 수 있다는 것이다.

이 아이디어는 우리가 직접 짜는 코드에만 쓰이는 게 아니다. 매일 쓰는 라이브러리 안에도 그대로 들어 있다. React가 리스트를 렌더링할 때 key를 요구하는 이유가 정확히 이것인데, 다음 글에서 그 이야기를 이어가려 한다.