JavaScript로 정렬된 세 배열의 교집합 구하기: 효율적인 알고리즘 가이드

이번 글에서는 오름차순으로 정렬된 세 개의 정수 배열을 입력받아, 세 배열 모두에 존재하는 공통 요소만 담은 새로운 배열을 반환하는 JavaScript 함수를 작성해 보겠습니다.

문제 이해하기

세 개의 정렬된 배열에서 세 배열 전체에 걸쳐 나타나는 값, 즉 교집합(intersection)을 찾는 것이 목표입니다.

예를 들어, 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr1 = [4, 7, 8, 11, 13, 15, 17];
const arr2 = [1, 3, 4, 13, 18];
const arr3 = [2, 4, 7, 8, 9, 10, 13];

세 배열 모두에 포함된 값은 4와 13뿐이므로, 기대하는 출력 결과는 다음과 같습니다.

const output = [4, 13];

접근 방식: 세 포인터를 활용한 선형 탐색

배열이 이미 정렬되어 있다는 점을 활용하면, 각 배열마다 하나씩 총 세 개의 포인터(인덱스)를 두고 앞에서부터 동시에 탐색하는 방법이 가장 효율적입니다.

동작 원리는 다음과 같습니다.

세 배열의 현재 위치 값을 비교하여 모두 같으면 결과 배열에 추가하고, 세 포인터를 모두 한 칸씩 앞으로 이동합니다.
값이 서로 다르다면, 세 값 중 가장 큰 값(max)보다 작은 값을 가진 배열의 포인터만 앞으로 이동시킵니다. 정렬된 상태이므로, 더 작은 값은 다른 배열에서 매칭될 가능성이 없기 때문입니다.

이 방식의 시간 복잡도는 O(n1 + n2 + n3)으로, 각 배열을 단 한 번씩만 순회하면 됩니다.

구현 코드

const arr1 = [4, 7, 8, 11, 13, 15, 17];
const arr2 = [1, 3, 4, 13, 18];
const arr3 = [2, 4, 7, 8, 9, 10, 13];

const intersectThree = (arr1 = [], arr2 = [], arr3 = []) => {
    let curr1 = 0;
    let curr2 = 0;
    let curr3 = 0;
    const res = [];

    while ((curr1 < arr1.length) && (curr2 < arr2.length) && (curr3 < arr3.length)) {
        // 세 배열의 현재 값이 모두 일치하는 경우
        if ((arr1[curr1] === arr2[curr2]) && (arr2[curr2] === arr3[curr3])) {
            res.push(arr1[curr1]);
            curr1++;
            curr2++;
            curr3++;
        }

        // 현재 위치 값들 중 최댓값을 구함
        const max = Math.max(arr1[curr1], arr2[curr2], arr3[curr3]);

        // 최댓값보다 작은 값을 가진 배열의 포인터만 이동
        if (arr1[curr1] < max) {
            curr1++;
        }
        if (arr2[curr2] < max) {
            curr2++;
        }
        if (arr3[curr3] < max) {
            curr3++;
        }
    }
    return res;
};

console.log(intersectThree(arr1, arr2, arr3));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

[4, 13]

정리

정렬된 여러 배열의 교집합을 구할 때는 해시맵이나 중첩 반복문 대신 다중 포인터(two-pointer 확장) 기법을 사용하는 것이 좋습니다. 각 배열을 한 번씩만 순회하므로 시간 복잡도가 선형(O(n)) 수준으로 유지되며, 추가 메모리 사용 없이 문제를 해결할 수 있습니다. 이 패턴은 리트코드(LeetCode)의 'Intersection of Three Sorted Arrays' 같은 문제에서 자주 활용되니 꼭 익혀두시길 바랍니다.