JavaScript로 두 배열의 교집합 구하기 — 중복 요소까지 정확히 처리하는 방법

문제 이해하기

두 개의 숫자 배열 arr1과 arr2를 인자로 받아, 두 배열에 공통으로 존재하는 모든 요소로 구성된 새로운 배열을 반환하는 JavaScript 함수를 작성해야 합니다.

여기서 핵심은 단순히 값의 존재 여부만 확인하는 것이 아니라, 동일한 요소가 양쪽 배열에 여러 번 등장할 경우 그 모든 인스턴스를 결과에 포함해야 한다는 점입니다. 즉, 중복 횟수까지 고려한 교집합(multiset intersection)을 구해야 합니다.

예제

입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr1 = [1, 2, 2, 4, 4, 5, 6];
const arr2 = [3, 2, 4, 2, 4, 9];

숫자 2는 arr1에 두 번, arr2에도 두 번 등장하므로 결과에 두 번 포함되어야 하고, 4 역시 마찬가지로 두 번씩 등장하므로 두 번 포함됩니다. 따라서 기대되는 출력은 다음과 같습니다.

const output = [2, 2, 4, 4];

접근 방식: Map 객체 활용

가장 효율적이고 직관적인 방법은 Map 객체를 활용하는 것입니다. 알고리즘의 흐름은 다음과 같습니다.

먼저 Map을 생성하여 arr2의 각 요소별 등장 횟수를 기록합니다.
arr1을 filter()로 순회하면서, Map에 해당 요소의 잔여 카운트가 남아 있으면 결과에 포함하고 카운트를 1 감소시킵니다.
카운트가 0이 되면 더 이상 매칭할 수 없으므로 해당 요소는 제외됩니다.

이렇게 하면 각 요소가 교집합에 포함될 수 있는 최대 횟수가 자연스럽게 min(빈도수₁, 빈도수₂)로 제한됩니다.

구현 코드

const arr1 = [1, 2, 2, 4, 4, 5, 6];
const arr2 = [3, 2, 4, 2, 4, 9];

const findIntersection = (arr1 = [], arr2 = []) => {
    const map = new Map();
    // arr2의 요소별 등장 횟수를 Map에 기록
    for (const el of arr2) {
        const count = map.get(el) || 0;
        map.set(el, count + 1);
    }
    // arr1을 순회하며 잔여 카운트가 있는 요소만 필터링
    return arr1.filter(el => {
        let count = map.get(el);
        if (count) {
            map.set(el, --count);
            return true;
        }
        return false;
    });
};

console.log(findIntersection(arr1, arr2));

실행 결과

[2, 2, 4, 4]

동작 원리 상세 설명

코드가 실행되는 과정을 단계별로 살펴보면 다음과 같습니다.

빈도수 기록: 첫 번째 루프에서 map은 { 3: 1, 2: 2, 4: 2, 9: 1 } 형태로 arr2의 빈도수를 저장합니다.
필터링: filter()가 arr1을 순회할 때, 요소 2를 만나면 map의 카운트(2)가 남아 있으므로 결과에 포함되고 카운트는 1로 감소합니다. 두 번째 2도 카운트(1)가 남아 있어 포함되며 카운트는 0이 됩니다.
카운트 소진: 이후 동일한 요소를 다시 만나면 카운트가 0이므로 falsy 판정을 받아 제외됩니다.

복잡도 분석

시간 복잡도: O(n + m) — 두 배열을 각각 한 번씩만 순회하며, Map의 조회·삽입 연산은 평균적으로 O(1)입니다.
공간 복잡도: O(m) — arr2의 고유 요소 수만큼 Map 메모리가 필요합니다.

중첩 루프와 splice()를 사용하는 나이브한 O(n × m) 방식과 달리, 이 접근법은 배열 크기가 커져도 선형 시간에 동작하므로 실무에서 권장되는 패턴입니다.