[JS 알고리즘] 두 집합의 공통 원소 추출 – 투 포인터 알고리즘(2)

• 문제
• 내가 푼 방식
• 왜 이 방식이 아닌가
• 정답
• 정답 해설

문제

A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성하세요.

입력 설명
첫 번째 줄에 집합 A의 크기 N(1 ≤ N ≤ 30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소는 중복되지 않습니다.
세 번째 줄에 집합 B의 크기 M(1 ≤ M ≤ 30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소는 중복되지 않습니다.
각 집합의 원소는 1,000,000,000 이하의 자연수입니다.

출력 설명
두 집합의 공통 원소를 오름차순으로 정렬하여 출력합니다.

입력 예제
5
1 3 9 5 2
5
3 2 5 7 8

출력 예제
2 3 5

내가 푼 방식

한 배열을 순회하면서 다른 배열에 포함되어 있는지 includes()로 확인하는 방식입니다.
공통 원소를 배열에 모은 뒤, 마지막에 정렬합니다.

function solution(arr1, arr2) {
    let arr = [];

    arr1.forEach((item) => {
        if (arr2.includes(item)) {
            arr.push(item);
        }
    });

    return arr.sort((a, b) => a - b);
}

왜 이 방식이 아닌가

includes()는 내부적으로 배열을 처음부터 끝까지 탐색합니다.
따라서 이 방식은 배열 크기가 커질수록 성능이 급격히 떨어집니다.

이 문제에서는 배열의 길이가 최대 30,000까지 가능하므로,
최악의 경우 O(N × M)에 가까운 시간이 걸릴 수 있습니다.
코딩 테스트에서는 이런 방식이 시간 초과로 이어질 가능성이 높습니다.

정답

두 배열을 먼저 오름차순으로 정렬한 뒤, 투 포인터 방식으로 공통 원소를 찾습니다.

function solution(arr1, arr2) {
    let answer = [];
    arr1.sort((a, b) => a - b);
    arr2.sort((a, b) => a - b);

    let p1 = 0;
    let p2 = 0;

    while (p1 < arr1.length && p2 < arr2.length) {
        if (arr1[p1] === arr2[p2]) {
            answer.push(arr1[p1]);
            p1++;
            p2++;
        } else if (arr1[p1] < arr2[p2]) {
            p1++;
        } else {
            p2++;
        }
    }

    return answer;
}

정답 해설

두 배열을 각각 오름차순으로 정렬하면, 가장 작은 값부터 차례대로 비교할 수 있는 상태가 됩니다.
이 상태에서 두 포인터를 사용하면 불필요한 비교 없이 공통 원소만 골라낼 수 있습니다.

arr1[p1]과 arr2[p2]가 같으면 공통 원소이므로 결과에 추가하고,
두 포인터를 모두 한 칸씩 이동합니다.

값이 다를 경우에는 더 작은 값을 가진 쪽 포인터만 이동합니다.
이렇게 하면 이미 비교가 끝난 값은 다시 볼 필요가 없습니다.

예제 디테일

기본 예제

console.log(solution([1, 3, 9, 5, 2], [3, 2, 5, 7, 8]));
// [2, 3, 5]

동작 설명: 두 배열을 정렬한 뒤, 작은 값부터 하나씩 비교합니다.
값이 같은 경우에만 결과 배열에 추가됩니다.

메커니즘 해설: 포인터는 한 방향으로만 이동하므로,
각 원소는 최대 한 번씩만 비교됩니다.

실수 포인트: 값을 추가한 뒤 포인터를 하나만 이동시키면
같은 값이 반복 비교되어 무한 루프에 빠질 수 있습니다.

응용 예제

console.log(solution([1, 2, 4, 6, 8], [2, 4, 6, 8, 10]));
// [2, 4, 6, 8]

동작 설명: 두 배열 모두 정렬되어 있으므로
포인터는 같은 값에서만 동시에 이동합니다.

메커니즘 해설: 중복이 없는 집합 조건 덕분에
결과에는 동일한 값이 한 번씩만 추가됩니다.

실수 포인트: 문제 조건에 "중복 없음"이 없다면
중복 처리 로직을 별도로 고려해야 합니다.

오류 예제

console.log(solution([3, 1, 5], [2, 3]));
// 정렬되지 않은 입력

동작 설명: 입력이 정렬되어 있지 않으면
포인터 비교 순서가 의미를 잃습니다.

메커니즘 해설: 투 포인터는 "앞에 있는 값이 더 작다"는
전제가 반드시 필요합니다.

실수 포인트: 이 문제는 정렬이 보장되지 않으므로
반드시 정렬 후에 투 포인터를 적용해야 합니다.