두 개의 숫자 배열이 주어졌을 때, 두 배열의 교집합을 계산하여 공통 요소들을 담은 배열을 반환하는 함수(예: intersection())를 작성해야 합니다. 이때 결과 배열의 각 요소는 두 배열에 나타난 횟수만큼 포함되어야 합니다.
예를 들어 다음과 같습니다.
입력: arr1 = [1,2,3,1], arr2 = [1,3,1]
출력: [1,3,1]
접근 방법
만약 두 배열이 이미 정렬되어 있다면 투 포인터(two pointer) 기법을 활용할 수 있습니다. 각 포인터를 두 배열의 시작 지점(인덱스 0)에 위치시킨 후, 조건에 따라 포인터를 증가시켜가며 비교하면 됩니다. 이 경우 시간 복잡도는 O(m+n)으로, m과 n은 각각 두 배열의 크기입니다.
하지만 배열이 정렬되어 있지 않다면, 굳이 정렬한 뒤 이 방식을 적용하는 것은 비효율적입니다. 대신 첫 번째 배열의 모든 값을 두 번째 배열과 하나씩 비교하여 교집합 배열을 만드는 방법을 사용할 수 있으며, 이 방법의 시간 복잡도는 O(n²)입니다.
이를 구현한 코드는 다음과 같습니다.
예제
const arr1 = [1, 2, 43, 5, 3, 7, 7, 8, 4, 2];
const arr2 = [1, 1, 6, 6, 2, 78, 7, 2, 3, 7, 23, 5, 3];
const intersection = (arr1, arr2) => {
const res = [];
const { length: len1 } = arr1;
const { length: len2 } = arr2;
const smaller = (len1 < len2 ? arr1 : arr2).slice();
const bigger = (len1 >= len2 ? arr1 : arr2).slice();
for(let i = 0; i < smaller.length; i++){
if(bigger.indexOf(smaller[i]) !== -1){
res.push(smaller[i]);
bigger.splice(bigger.indexOf(smaller[i]), 1, undefined);
}
};
return res;
};
console.log(intersection(arr1, arr2));
코드 동작 원리
위 코드는 먼저 두 배열 중 더 짧은 배열을 기준으로 반복문을 수행하여 불필요한 연산을 줄입니다. 이후 bigger 배열에서 indexOf() 메서드로 현재 값이 존재하는지 확인하고, 존재한다면 결과 배열에 해당 값을 추가합니다.
핵심은 splice()를 사용해 매칭된 요소를 undefined로 치환하는 부분입니다. 이렇게 하면 이미 사용된 요소가 다시 매칭되는 것을 방지할 수 있어, 결과 배열에는 각 요소가 두 배열에 실제로 나타난 횟수만큼 정확하게 포함됩니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[1, 2, 5, 3, 7, 7, 2]