[LeetCode] Move Zeroes (JAVA)

문제

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

 

입출력 및 제약 사항

 

풀이

간단한 투 포인터 문제였습니다.

맨 뒤에 부터 한 칸씩 앞쪽으로 탐색하면서 0일 경우에는 해당 요소와 그 다음 요소를 맨 뒤까지 스왑하면 됩니다.

가령 [1, 2, 0, 0, 3] 배열이 주어진 경우, 다음과 같은 의사 과정을 거칩니다.

 

1. "3"은 0이 아니므로 왼쪽 숫자를 탐색한다.

2. 현재 요소가 "0"이므로 다음 요소와 스왑한다. [1, 2, 0, 3, 0]

3. 현재 요소가 "0"이므로 다음 요소와 스왑한다. [1, 2, 3, 0, 0]

4. 이후 요소는 0이 없으므로 스왑 과정을 멈춘다.

 

0은 맨 뒤까지 밀어야 하므로 스왑 횟수가 여러 번 수행될 수 있다는 점을 염두해야 합니다. 최대 시간 복잡도는 O(N^2)이긴 하지만, 최대 배열의 길이가 10,000이므로 시간 초과가 발생하지는 않습니다.

 

아래는 위 로직을 정리한 소스 코드입니다.

 

소스 코드

class Solution {
    public void moveZeroes(int[] nums) {
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] != 0) {
                continue;
            }
            for (int j = i; j < nums.length - 1; j++) {
                swap(nums, j, j + 1);
            }
        }
    }
    
    public void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}