듣보잡(백준 1764번) 문제를 풀던 중, 단순 배열 비교에서 시간 초과가 발생했다.
🔍 이유 설명
문제의 원인은 includes()와 filter를 사용했기 때문이었다.
이 경우 시간 복잡도는 O(N * M) 정도로 커지고, 최대 입력이 (N, M ≤ 500,000)일 경우 2.5억 번 이상 비교가 발생해서 시간 초과가 발생한다.
따라서 set과 has()를 이용하여 코드를 수정하였다.
// 느린 방식 (시간 초과 가능성)
arr1.filter(x => arr2.includes(x)); // O(N * M)
// 빠른 방식
const set2 = new Set(arr2);
arr1.filter(x => set2.has(x)); // O(N)✅ Array vs Set vs Map
Set
- O(1) 평균 시간 복잡도로
.has()로 존재 여부 확인 가능 (해시 테이블 기반) - 중복 허용 안 함, key만 저장 → 구조가 단순
- 메모리, 속도 모두 효율적
- 존재 여부를 확인할 때 최적
Map
- O(1) 평균 시간 복잡도로
.has(key)/.get(key)존재 여부 확인 가능 - key-value 쌍 저장 →
Set보다 메모리 사용량 ↑ - key만 필요할 경우엔
Set보다 비효율적
Array
.includes()는O(N)시간 복잡도- 값을 순차 탐색해야 하므로 느림
- 메모리 구조는 단순하지만, 성능에서는 뒤쳐짐
요약 정리
| 목적 | 배열(Array) | Set | Map |
|---|---|---|---|
| 순서 유지 | ✅ | 🔸 (삽입 순서 유지되지만 권장 X) | 🔸 |
| 중복 허용 | ✅ | ❌ | ✅ (Key는 고유) |
| 존재 여부 검사 | ❌ O(N) .includes() | ✅ O(1) .has() | ✅ O(1) .has(key) |
| 키-값 구조 필요 | ❌ | ❌ | ✅ |
| 반복적 존재 여부 검사 | ❌ 비효율적 | ✅ 가장 적합 | ✅ 가능하지만 무거움 |
| 값만 저장할 때 | ✅ | ✅ 가장 경량 | ❌ 낭비 |
- 중복 없고, 값 존재 여부만 빠르게 확인 :
Set - 순서 유지가 중요, 단순한 데이터 흐름 처리(정렬/출력 등):
Array - key-value 저장이 필요:
Map
