JavaScript로 두 문자열 배열의 교집합(공통 요소) 구하기

두 개의 문자열 배열이 주어졌을 때, 두 배열의 교집합(intersection)을 계산하여 공통 요소들을 배열 형태로 반환하는 함수를 작성해야 합니다. 이때 결과 배열에 포함되는 각 요소는 양쪽 배열에서 나타난 횟수만큼 중복되어 표현되어야 합니다.

예시

입력이 다음과 같다면 −

arr1 = ['hello', 'world', 'how', 'are', 'you'];
arr2 = ['hey', 'world', 'can', 'you', 'rotate'];

출력은 다음과 같아야 합니다 −

['world', 'you'];

접근 방법

만약 두 배열이 이미 정렬되어 있다면, 각각의 시작 지점(인덱스 0)에 포인터를 둔 후 조건에 따라 해당 포인터를 증가시키는 투 포인터(two-pointer) 기법을 활용할 수 있습니다. 이 경우 시간 복잡도는 배열의 크기를 m과 n이라 할 때 O(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]);
            // 이미 매칭된 요소는 undefined로 대체하여 중복 매칭 방지
            bigger.splice(bigger.indexOf(smaller[i]), 1, undefined);
        }
    };
    return res;
};
console.log(intersectElements(arr1, arr2));

코드 설명

이 함수는 먼저 두 배열의 길이를 비교하여 더 짧은 배열을 기준으로 삼습니다. 그런 다음 짧은 배열의 각 요소가 긴 배열에 존재하는지 indexOf()로 확인하고, 존재한다면 결과 배열에 추가합니다. 동시에 splice()를 사용해 해당 요소를 undefined로 치환함으로써, 같은 요소가 한 번만 매칭되도록 처리합니다. 이렇게 하면 각 요소가 양쪽 배열에 나타나는 횟수만큼 정확하게 결과에 반영됩니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

[ 'world', 'you' ]