js 에서 중복되는 값 처리를 할 때 나는 주로 arr.filter((el, idx) => el !== arr[idx]) 이런 식으로 filter를 이용해서 처리해왔는데, 최근에 set 자료구조를 이용하는건 어떤지 궁금해졌어. 시간복잡도나 공간복잡도 관점에서 볼 때 뭐가 더 나은 선택인지 비교 분석해줘
1. filter()를 이용한 방법
const unique = arr.filter((el, idx) => arr.indexOf(el) === idx);
작동 방식
filter()는 배열의 각 요소를 순회하면서 indexOf()를 통해 해당 요소가 처음 등장한 인덱스와 현재 인덱스를 비교합니다.
중복된 요소는 조건에 의해 필터링됩니다.
시간 복잡도
arr.indexOf(el)는 배열의 처음부터 해당 요소를 찾기 때문에 **O(n)**입니다.
filter()는 배열 전체를 순회하기 때문에 **O(n)**입니다.
최악의 경우 시간 복잡도는 O(n²) (중첩된 순회).
공간 복잡도
원본 배열과 동일한 크기의 결과 배열이 필요하므로 **O(n)**입니다.
추가적인 메모리는 사용하지 않으나, indexOf()의 호출이 많아지면 메모리 캐싱 효율이 떨어질 수 있습니다.
2. Set을 이용한 방법
const unique = [...new Set(arr)];
작동 방식
Set은 내부적으로 중복을 허용하지 않는 데이터 구조입니다.
배열을 Set으로 변환하면 중복이 자동으로 제거됩니다.
이후 다시 스프레드 연산자(...)를 사용하여 배열로 변환합니다.
시간 복잡도
Set의 삽입 연산은 평균적으로 **O(1)**입니다.
배열의 요소를 Set에 삽입하는 전체 과정은 **O(n)**입니다.
스프레드 연산자로 배열로 변환하는 과정도 **O(n)**입니다.
전체 시간 복잡도는 O(n).
공간 복잡도
Set은 추가적인 자료구조를 사용하므로 메모리 사용량은 원본 배열의 크기만큼 증가합니다.
최종 배열을 생성하므로 결과적으로 O(n).
비교
| 측면 | filter() | Set |
|---|
| 시간 복잡도 | O(n²) (최악의 경우) | O(n) (평균적으로 더 효율적) |
| 공간 복잡도 | O(n) | O(n) |
| 가독성 | 상대적으로 복잡 | 간단하고 직관적 |
| 호환성 | 오래된 JS 환경에서도 사용 가능 | 최신 JS 엔진에서 성능 최적화된 구현 |
권장사항
1. 대규모 데이터:
Set을 사용하는 것이 성능 면에서 훨씬 유리합니다.
시간 복잡도가 낮기 때문에 큰 배열에서도 빠르게 동작합니다.
2. 작거나 제한된 데이터:
filter()도 충분히 동작합니다.
특히, indexOf()를 통해 특정 순서를 보존해야 할 때 유용합니다.
3. 가독성:
코드의 단순성을 원한다면 Set을 사용하는 것이 더 깔끔합니다.
결론
대부분의 경우 Set을 사용하는 방법이 성능과 가독성 측면에서 우수합니다. 다만, 특정 배열의 특수한 순서 보존이나 구형 JS 환경을 고려해야 하는 경우에는 filter() 방식이 적합할 수 있습니다.
