JavaScript에서 배열의 0을 끝으로 이동하는 제자리 알고리즘 구현하기

문제 개요

정수 배열 arr가 주어졌다고 가정해 보겠습니다. 배열을 제자리(in-place)에서 수정하여 모든 0을 배열의 뒤쪽으로 이동시키는 함수를 작성해야 합니다.

이때 중요한 조건은 0이 아닌 다른 요소들의 상대적인 순서가 그대로 유지되어야 한다는 점입니다.

예시

입력 배열이 다음과 같다면,

const arr = [0, 11, 0, 22, 67];

배열은 다음과 같이 수정되어야 합니다.

const output = [11, 22, 67, 0, 0];

해결 알고리즘

이 문제는 투 포인터(two-pointer) 기법으로 효율적으로 해결할 수 있습니다. 포인터 i는 배열을 순회하며 0이 아닌 요소를 찾고, 포인터 j는 0이 아닌 요소가 위치할 자리를 가리킵니다. 순회가 끝난 후에는 j 이후의 모든 자리를 0으로 채우면 됩니다.

구현 코드

다음은 전체 코드입니다.

const arr = [0, 11, 0, 22, 67];
const moveZeroToEnd = (arr = []) => {
    const swap = (array, ind1, ind2) => {
        const temp = array[ind1];
        array[ind1] = array[ind2];
        array[ind2] = temp;
    };
    let j = 0;
    for (let i = 0; i < arr.length; ++ i) {
        if (arr[i] !== 0) {
            swap(arr, i, j++);
        }
    }
    while (j < arr.length) {
        arr[j++] = 0;
    };
};
moveZeroToEnd(arr);
console.log(arr);

출력 결과

다음은 콘솔 출력 결과입니다.

[11, 22, 67, 0, 0]

알고리즘 동작 원리

이 코드의 시간 복잡도는 O(n)이며, 추가 배열을 사용하지 않고 기존 배열만 수정하므로 공간 복잡도는 O(1)입니다. 핵심 동작 과정은 다음과 같습니다.

• 포인터 j는 항상 다음에 0이 아닌 값이 들어갈 위치를 가리킵니다.
• arr[i]가 0이 아니면 i와 j 위치의 값을 서로 교환(swap)한 후 j를 1 증가시킵니다.
• 모든 순회가 끝나면 인덱스 j부터 배열 끝까지 남은 자리를 모두 0으로 채웁니다.

이 방식 덕분에 0이 아닌 요소들의 원래 순서는 그대로 유지되면서, 모든 0이 배열의 뒤쪽으로 이동하게 됩니다.