코딩테스트 투 포인터 풀이: 공통 원소 추출하기

내가 푼 방식

한 배열을 순회하면서 다른 배열에 포함되어 있는지 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]가 같으면 공통 원소이므로 결과에 추가하고,
두 포인터를 모두 한 칸씩 이동합니다.

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

공통 원소 추출 전에 투 포인터 기본 이동 방식을 먼저 잡고 싶다면 JS 투 포인터 배열 합치기를 함께 복습하면 좋습니다.

두 배열 공통 원소 문제의 핵심이 되는 포인터 이동 방식은 JS 연속 구간 합 투 포인터에서 기본 패턴으로 정리됩니다.

예제 디테일

기본 예제

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]));
// 정렬되지 않은 입력

동작 설명: 현재 solution은 내부에서 정렬하므로 이 호출의 실제 결과는 [3]이며 오류가 아닙니다. 정렬 두 줄을 제거한 변형에서만 포인터 전제가 깨집니다.

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

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

복잡도·입력 조건·검증 체크리스트

includes()를 각 원소마다 호출하는 첫 풀이는 최악의 경우 N×M번에 가까운 비교가 필요합니다. 정답 풀이는 두 배열 정렬에 O(N log N + M log M), 두 포인터 순회에 O(N+M)이 듭니다. 이미 정렬된 입력이라면 순회 부분만 O(N+M)이지만, 이 문제의 원본 입력은 정렬을 보장하지 않으므로 전체 복잡도에서 정렬 비용을 빼면 안 됩니다.

Array.prototype.sort()는 원본 배열을 제자리에서 바꾸며, 숫자를 오름차순으로 정렬하려면 (a, b) => a - b 비교 함수를 전달해야 합니다. 호출자가 원본을 계속 써야 한다면 [...arr1].sort(...)처럼 복사본을 정렬하세요. 자세한 동작은 MDN Array.prototype.sort() 문서에서 확인할 수 있습니다.

console.assert(JSON.stringify(solution([1, 3, 9, 5, 2], [3, 2, 5, 7, 8])) === '[2,3,5]');
console.assert(JSON.stringify(solution([], [1, 2])) === '[]');
console.assert(JSON.stringify(solution([4], [4])) === '[4]');

문제는 각 집합 안의 원소가 중복되지 않는다고 명시합니다. 중복을 허용하면 현재 코드는 두 배열에 존재하는 횟수의 최솟값만큼 결과에 넣는 다중집합 교집합처럼 동작하므로, ‘고유값만 한 번’이 목표라면 별도의 중복 제거 규칙이 필요합니다.

결과 원소 수를 K라고 하면 정답 배열에는 O(K) 공간이 필요합니다. 원본 보존을 위해 두 배열을 복사해 정렬하면 여기에 O(N+M) 복사 공간이 추가됩니다. 반대로 현재 코드처럼 제자리 정렬하면 복사 공간은 줄지만 호출 뒤 입력 순서가 달라집니다. 어느 선택이 맞는지는 함수 계약에 포함해야 합니다.

정리: 먼저 입력의 정렬 여부와 중복 정책을 확인하고, 정렬 비용·원본 변경 여부까지 설명할 수 있어야 완성된 풀이입니다. 이 조건을 적은 뒤 포인터가 한 방향으로만 이동한다는 불변식을 제시하면 시간 복잡도 설명도 명확해집니다.