두 개의 숫자 배열, 예를 들어 arr1과 arr2를 인자로 받는 JavaScript 함수를 작성해야 합니다. 이 함수의 목표는 두 배열에 모두 존재하는 요소, 즉 두 배열의 교집합을 찾아내는 것입니다.
여기서 중요한 조건이 하나 있습니다. 한 번 교집합으로 확인된 요소는 이후에 두 배열에서 다시 등장하더라도 결과에 중복해서 포함되어서는 안 됩니다. 즉, 각 교집합 요소는 결과 배열에 단 한 번만 나타나야 합니다.
예시
입력 배열이 다음과 같다고 가정해 보겠습니다.
const arr1 = [1, 5, 7, 3, 1]; const arr2 = [1, 7, 3, 1, 6];
이 경우 기대하는 출력 결과는 다음과 같습니다.
const output = [1, 3, 7];
결과 배열 내 요소들의 순서는 크게 중요하지 않습니다. 핵심은 중복된 교집합 요소를 제거하고 각 값을 한 번씩만 포함하는 것입니다. 위 예시에서 숫자 1은 두 배열에 여러 번 등장하지만, 결과에는 딱 한 번만 포함됩니다.
해결 방법: Set 활용
이 문제는 Set 객체를 사용하면 효율적으로 해결할 수 있습니다. Set은 중복을 허용하지 않고 값의 존재 여부를 빠르게 확인할 수 있는 자료구조이기 때문입니다. 알고리즘의 흐름은 다음과 같습니다.
- 첫 번째 배열의 모든 요소를 Set에 추가합니다.
- 두 번째 배열을 순회하면서, 현재 요소가 Set에 존재하는지 확인합니다.
- 존재한다면 해당 요소를 결과 배열에 넣고, Set에서 즉시 삭제하여 같은 값이 다시 추가되지 않도록 합니다.
다음은 실제 구현 코드입니다.
const arr1 = [1, 5, 7, 3, 1];
const arr2 = [1, 7, 3, 1, 6];
const uniqueIntersection = (arr1, arr2) => {
const map = new Set();
const res = [];
// 첫 번째 배열의 요소들을 Set에 저장
arr1.forEach(el => map.add(el));
// 두 번째 배열을 순회하며 교집합 찾기
arr2.forEach(el => {
if (map.has(el)) {
res.push(el);
map.delete(el); // 중복 방지를 위해 삭제
};
});
return res;
};
console.log(uniqueIntersection(arr1, arr2));실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[1, 7, 3]
코드 설명
먼저 arr1의 모든 요소를 Set에 담습니다. 그런 다음 arr2를 순회하면서 각 요소가 Set에 있는지 검사합니다. 만약 존재한다면 그 요소는 두 배열의 공통 요소이므로 결과 배열 res에 추가하고, 동시에 Set에서 삭제합니다. 이렇게 하면 동일한 값이 뒤에서 다시 등장하더라도 map.has() 조건을 통과하지 못해 중복이 자연스럽게 걸러집니다.
이 방식의 시간 복잡도는 O(n + m)으로, n과 m은 각각 두 배열의 길이입니다. Set의 삽입과 조회가 평균적으로 상수 시간에 이루어지기 때문에, 중첩 반복문을 사용하는 단순 비교 방식(O(n × m))보다 훨씬 효율적입니다.