[JavaScript] 집합(Set) 자료형 사용하여 시간복잡도 줄이기

728x90

a배열을 반복하며 b배열에 a의 값과 일치하는 값이 있다면 a[?] 값을 1로 변경해야 한다.

// 예시 데이터
let a = [
    { id: 1, value: 0 },
    { id: 2, value: 0 },
    { id: 3, value: 0 }
];

let b = [
    { id: 2, value: 1 },
    { id: 4, value: 1 }
];

기존 로직 - 이중 반복문

기존에는 배열을 순차적으로 돌며 값을 비교하기 위한 가장 쉬운 방법인 이중 반복문을 사용하였다.

a 배열의 크기만큼 (i)를 반복한다.
b 배열의 크기만큼 (j)를반복한다.
a배열의 i와 b배열의 j번째 값을 비교한다.
값이 일치한다면 a[i]를 1로 변경한다.

for (let i = 0; i < a.length; i++) { 
   for (let j = 0; j < b.length; j++) { 
      if (a[i].id === b[j].id) { 
       	 a[i].value = 1; 
      } 
   } 
}

외부 반복문이 a.length만큼, 내부 반복문이 b.length만큼 실행되므로, 시간 복잡도는 O(a.length * b.length)이다.
이 방법은 두 배열의 크기에 따라 매우 비효율적일 수 있다.

개선 로직 - Set의 has 비교

기존 로직에서는 이중 반복문을 사용하여 a*b 만큼의 반복을 수행하기 때문에 배열의 크기가 조금만 커져도 서비스에 부하가 매우 많이 늘어나게 된다. 이러한 이유로 이중 반복문을 제거하기 위해 Set 타입의 has() 함수를 사용할 수 있다.

b 배열을 Set 타입으로 변환한다.
a 배열의 크기만큼 (i)를 반복한다.
bSet 집합에 a배열의 id 값이 있는지 확인한다.
값이 존재한다면 a[i]를 1로 변경한다.

const bSet = new Set(b.map(item => item.id));
for (let i = 0; i < a.length; i++) { 
   if (bSet.has(a[i].id)) {
      a[i].value = 1; 
   } 
}

먼저 b 배열에서 id 값을 추출해 Set으로 변환하는데, 이는 O(b.length) 시간이 걸린다.

그런 다음, a 배열을 한 번 반복하면서 Set의 has 메서드를 사용해 id를 확인하는데, Set.has()는 평균적으로 O(1)에 가까운 시간 복잡도를 가지기 때문에 bSet의 크기에 영향이 없다.

따라서 이 방법의 총 시간 복잡도는 O(b.length) + O(a.length) = O(a.length + b.length)이다.

결론 :

이중 반복문: O(a.length * b.length)
Set을 사용한 방법: O(a.length + b.length)

b 배열을 Set으로 변환하여 처리하는 방법도 결국 내부적으로는 Array -> Set으로 변환할 때 반복 작업이 발생된다. 하지만 a 배열의 반복문에 대한 영향도는 없어지기 때문에 a와 b의 시간 복잡도가 + 기호로 바뀐다.

즉, Set을 사용하는 방법이 이중 반복문보다 훨씬 더 효율적이다. 두 배열의 크기가 클수록 차이가 더 커지며, Set을 사용하면 시간 복잡도가 선형적으로 줄어든다.

💡배열(Array) 타입에도 값의 포함 여부를 확인할 수 있는 includes() 함수가 있지만 분명한 성능 차이가 존재한다.

1. 집합(Set)의 has() 함수

Set은 중복되지 않는 값들의 집합이며, has() 함수를 통해 값이 집합에 존재하는지 확인할 수 있다.
시간 복잡도는 O(1)에 가깝다.
Map도 Set과 같은 has() 함수를 사용할 수 있다.

const set = new Set([1, 2, 3]);
console.log(set.has(2)); // true

2. 배열(Array)의 includes() 함수

배열(Array)은 순차적으로 값을 저장하는 자료구조이므로, 포함 여부를 확인할 때 includes() 메서드를 사용할 수 있다.
하지만, 이는 내부적으로 모든 항목을 하나씩 비교하므로 O(n) 시간이 소요됩니다.

const list = [1, 2, 3]; 
console.log(list.includes(2)); // true

includes()는 작은 크기의 배열에서는 괜찮지만, 리스트가 커질수록 성능에 영향이 있을 수 있다.

성능 비교

집합(Set): has() 메서드를 사용하여 빠르게 포함 여부를 확인하며, 평균 시간 복잡도는 O(1)이다.
리스트(Array): includes() 메서드를 사용하면 전체 리스트를 순회하면서 확인하므로 시간 복잡도는 O(n)이다.

왜 Array의 includes()는 O(n)이고, Set의 has()는 O(1)의 시간 복잡도를 가지는가?

Set은 해시 테이블(Hash Table)을 기반으로 동작한다.
값이 추가될 때 해시 함수가 실행되어 해당 값이 특정 위치에 저장된다. has() 메서드는 해시 테이블의 구조를 이용해 값을 직접 조회하므로, 대부분의 경우 시간 복잡도는 O(1)이다.
즉, Set은 값이 존재하는지 한 번의 해시 계산으로 빠르게 확인할 수 있다. 그렇기 때문에 값이 많아지더라도 성능이 거의 영향을 받지 않는다.

- 끝 -