[Question] 9. 0을 배열의 오른쪽으로 옮기기

* 본 문제와 풀이의 저작권은 매일프로그래밍에 있습니다.

정수 배열이 주어지면 0이 아닌 정수의 순서를 유지하며 모든 0을 배열의 오른쪽으로 옮겨라

예제 }

Input : [0, 5, 0, 3, -1]

Output : [5, 3, -1, 0, 0]

Input : [3, 0, 3]

Output : [3, 3, 0]

이 문제는 0을 오른쪽으로 옮기는 것보다 0이 아닌 정수를 왼쪽으로 옮긴다고 생각하면 쉽게 풀 수 있다.

void solve(int[] input) {
    int position = 0; // 0이 아닌 정수가 들어갈 곳

    for (int i = 0; i < input.length; i++) {
        if (input[i] != 0) {
            swap(input, i, position);
            position++;
        }
    }
}

void swap(int[] arr, int a, int b) {
    if (a == b) return;
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

시간 복잡도: O(n)

공간 복잡도: O(1)