코딩테스트 투 포인터 풀이: 두 정렬 배열 합치기

내가 푼 방식

두 배열을 합친 뒤 sort()로 다시 정렬하는 방식입니다.
구현은 쉽지만, 이 문제의 의도(정렬된 상태 활용)와는 다릅니다.

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

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

동작: 합치고 정렬합니다. 결과는 맞게 나옵니다.

왜 이 방식이 아닌가

이 문제는 두 배열이 이미 정렬되어 있다는 조건을 줍니다.
즉, 다시 정렬하지 말고 “병합”만 하라는 의미입니다.

sort()는 (N+M)log(N+M)만큼 비교가 생깁니다.
반면 투 포인터 병합은 각 원소를 한 번씩만 보고 끝나서 O(N + M)입니다.
출력만 채점하는 문제에서는 제한 시간 안에 끝나면 정답이 될 수 있지만, 정렬 조건을 활용하는 출제 의도와 선형 복잡도를 보여주지는 못합니다.

정답

투 포인터로 두 배열을 동시에 보면서 작은 값부터 결과에 넣습니다.

같은 투 포인터의 양쪽 포인터 비교 방식은 중복 원소 비교 문제에서도 자주 쓰입니다. JS 투 포인터 공통 원소 추출로 확장해보면 비교 기준이 더 분명해집니다.

function solution(arr1, arr2) {
    let answer = [];
    let p1 = 0;
    let p2 = 0;

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

    while (p1 < arr1.length) {
        answer.push(arr1[p1]);
        p1++;
    }

    while (p2 < arr2.length) {
        answer.push(arr2[p2]);
        p2++;
    }

    return answer;
}

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

정답 해설

1) arr1[p1]과 arr2[p2]를 비교합니다.
2) 더 작은 값을 결과 배열에 넣습니다.
3) 넣은 쪽 포인터만 1칸 이동합니다.

한쪽 배열이 끝나면, 다른 배열의 남은 값은 이미 정렬되어 있으므로 그대로 이어 붙이면 됩니다.

시간 복잡도는 O(N + M)입니다.
포인터가 뒤로 가지 않아서 각 원소를 최대 한 번만 처리합니다.
JS 연속부분수열 투 포인터는 배열값이 양수인 경우 구간 합을 확장/축소하는 방식으로 같은 패턴을 다른 형태로 연습할 수 있습니다.

예제 디테일

기본 예제

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

동작: 두 포인터가 왼쪽부터 비교하며 작은 값을 순서대로 넣습니다.

메커니즘: 이미 정렬되어 있으니, 현재 작은 값을 선택해도 전체 순서가 깨지지 않습니다.

실수 포인트: 한쪽 배열이 끝난 뒤 남은 값을 붙이는 코드를 빼먹기 쉽습니다.

응용 예제

console.log(solution([-5, -1, 4, 10], [-3, 0, 0, 7]));
// [-5, -3, -1, 0, 0, 4, 7, 10]

동작: 음수와 중복이 있어도 비교 규칙은 동일합니다.

메커니즘: 값의 크기 범위는 상관없고, 정렬되어 있다는 조건만 중요합니다.

실수 포인트: 중복 처리에서 조건을 <로만 두면 결과 순서가 달라 보일 수 있습니다.
보통 <=로 한쪽 기준을 고정해 혼란을 줄입니다.

오류 예제

console.log(solution([3, 1, 5], [2, 6]));
// 입력이 정렬되어 있지 않으면 전제가 깨집니다.

동작: 투 포인터는 “뒤에 더 작은 값이 없다”고 가정합니다.

메커니즘: [3, 1, 5]처럼 정렬이 깨져 있으면 비교 선택이 틀어질 수 있습니다.

실수 포인트: 문제에 정렬이 보장되지 않으면 먼저 정렬해야 합니다.
이 문제는 정렬이 보장되므로 그 전제를 그대로 사용합니다.

개선 예제

function solutionFast(arr1, arr2) {
    const n = arr1.length;
    const m = arr2.length;
    const answer = new Array(n + m);

    let p1 = 0;
    let p2 = 0;
    let i = 0;

    while (p1 < n && p2 < m) {
        if (arr1[p1] <= arr2[p2]) {
            answer[i] = arr1[p1];
            p1++;
        } else {
            answer[i] = arr2[p2];
            p2++;
        }
        i++;
    }

    while (p1 < n) {
        answer[i] = arr1[p1];
        p1++;
        i++;
    }

    while (p2 < m) {
        answer[i] = arr2[p2];
        p2++;
        i++;
    }

    return answer;
}

동작: 정답 풀이와 같지만, 배열을 미리 만들고 인덱스로 채웁니다.

메커니즘: 데이터가 매우 큰 경우 push()보다 예측 가능한 동작을 기대할 수 있습니다.

실수 포인트: 인덱스 i 증가를 빼먹으면 값이 덮어써지거나 빈칸이 남습니다.

방식 비교 표

선택 기준: 코딩 테스트(정렬 보장)라면 투 포인터가 우선입니다.
입력이 작고 빠르게 끝내야 하는 작업이라면 sort()도 실무에서 선택될 수 있습니다.

복잡도·정렬 전제·검증 체크리스트

투 포인터 병합은 각 원소를 한 번씩만 결과에 넣어 O(N+M) 시간과 결과 배열 O(N+M) 공간을 사용합니다. 합친 뒤 다시 정렬하면 일반적으로 O((N+M) log(N+M))으로 설명하지만, JavaScript sort()의 구체적인 시간·공간 복잡도는 엔진 구현에 따라 달라질 수 있습니다.

sort()는 원본을 제자리에서 바꾸고, 비교 함수를 생략하면 숫자도 문자열로 바꿔 UTF-16 순서로 비교합니다. 따라서 숫자 배열에는 (a, b) => a - b가 필요합니다. 정확한 계약은 MDN Array.prototype.sort() 문서에서 확인하세요.

console.assert(JSON.stringify(solution([], [1, 2])) === '[1,2]');
console.assert(JSON.stringify(solution([1, 2], [])) === '[1,2]');
console.assert(JSON.stringify(solution([1, 1], [1, 2])) === '[1,1,1,2]');

한쪽 배열이 비었을 때, 같은 값이 양쪽에 있을 때, 음수와 0이 섞였을 때를 따로 검증하세요. 입력이 정렬되지 않았다면 이 알고리즘의 전제가 깨지므로 호출 전에 정렬하거나 별도의 오류 정책을 둬야 합니다.

정리: 출력형 채점은 결과와 제한 시간으로 판단하므로 작은 입력에서는 재정렬 풀이도 통과할 수 있습니다. 그래도 문제에서 제공한 정렬 조건을 활용해 선형 병합을 구현하고, 남은 원소 처리까지 증명하는 것이 이 유형의 핵심입니다.