두 개의 배열이 주어졌을 때, 두 배열의 교집합을 계산하여 공통 요소들을 담은 배열을 반환하는 함수(예: intersection())를 작성해야 합니다. 결과 배열의 각 요소는 두 배열에 나타난 횟수만큼 포함되어야 하며, 요소의 순서는 상관없습니다.
문제 예시
예를 들어 다음과 같은 입력이 있다고 가정해 보겠습니다.
arr1 = ['hello', 'world', 'how', 'are', 'you']; arr2 = ['hey', 'world', 'can', 'you', 'rotate'];
두 배열에 공통으로 존재하는 요소는 'world'와 'you'이므로, 출력은 다음과 같아야 합니다.
Output: ['world', 'you'];
접근 방법
만약 배열이 미리 정렬되어 있다면 투 포인터(two pointer) 기법을 활용할 수 있습니다. 각 배열의 시작 지점(인덱스 0)에 포인터를 하나씩 두고, 값의 크기를 비교하면서 조건에 맞는 포인터를 증가시켜 나가는 방식입니다. 이 경우 시간 복잡도는 O(m+n)으로 매우 효율적이며, 여기서 m과 n은 각 배열의 크기입니다.
하지만 이번 문제에서 다루는 배열은 정렬되어 있지 않습니다. 정렬되지 않은 배열에 투 포인터 기법을 쓰려면 먼저 정렬을 수행해야 하는데, 이는 추가적인 비용이 발생하므로 비효율적입니다. 따라서 첫 번째 배열의 모든 값을 두 번째 배열과 하나씩 비교하여 교집합 배열을 만드는 완전 탐색 방식을 사용합니다. 이 방법의 시간 복잡도는 O(n²)입니다.
코드 예제
다음은 전체 구현 코드입니다.
arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];
const intersectElements = (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(intersectElements(arr1, arr2));코드 동작 원리
이 코드는 먼저 두 배열의 길이를 비교하여 더 짧은 배열을 smaller로, 더 긴 배열을 bigger로 분리합니다. 이후 smaller 배열의 각 요소가 bigger 배열에 존재하는지 indexOf()로 확인하고, 존재한다면 결과 배열에 추가한 뒤 bigger 배열에서 해당 요소를 undefined로 대체합니다. 이렇게 하면 한쪽 배열에 동일한 값이 여러 개 있을 때 중복으로 매칭되는 것을 방지할 수 있습니다.
또한 slice()를 호출하여 배열의 복사본을 생성하기 때문에 원본 배열은 변경되지 않고 그대로 유지된다는 점도 주목할 만합니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
[ 'world', 'you' ]