[LeetCode] 283번: Move Zeroes - Java

https://leetcode.com/problems/move-zeroes/

Move Zeroes - LeetCode

문제 설명

배열에 있는 0들을 오른쪽으로 모두 보내면 된다. 주의할 점은 요소들의 순서가 바뀌면 안 된다는 것이다. 문제는 단순하지만 시간 복잡도를 생각하면서 푼다면 조금 생각해야 한다. 

풀이 방법 1: 완전 탐색 - O(n^2)

버블 방식으로 모든 수를 비교해 가면서 0을 뒤로 미는 방식이다. 가장 단순하게 해결할 수 있지만 그만큼 효율적이지 못하다.

public void bubble(int[] nums) {
    for (int end = nums.length - 1; end >= 0; end--) {
        if (nums[end] != 0) {
            continue;
        }
        for (int start = end; start < nums.length - 1; start++) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
        }
    }
}

풀이 방법 2: 투 포인터 - O(n)

투 포인터 기법을 사용하면 시간 복잡도를 O(n)까지 줄일 수 있다. 이 기법을 활용한 두 가지 방법이 있다.

1. 스왑

맨 앞을 기준으로 잡고 반복하면서 0이 아닌 수는 nums[wIdx]와 스왑한다. 그리고 wIdx 값을 증가시킨다. 풀이 방법 1과 차이점은 포인터의 사용 유무이다. 풀이 방법 1은 단순히 모든 요소를 이중 반복문으로 순회하며 값을 비교한다. 이 방법은 포인터 하나를 따로 두기 때문에 반복문 하나로 순회가 가능하다. 맨 앞 요소가 0이 아니라도 상관없다. 어차피 맨 앞 요소가 0이 아니라면 따로 둔 포인터와 순회하는 인덱스 변수가 함께 증가하기 때문이다.

private void swap(int[] nums) {
    int wIdx = 0;
    for (int idx = 0; idx < nums.length; idx++) {
        if (nums[idx] != 0) {
            int tmp = nums[wIdx];
            nums[wIdx] = nums[idx];
            nums[idx] = tmp;

            wIdx++;
        }
    }
}

2. 복사

다른 방법으로는 복사하는 방식으로 접근이 있다. 이 또한 포인터 변수를 하나 두고 순회한다. 그러다 0이 아닌 수를 만나면 nums[wIdx]에 nums[idx]로 복사한다. 그리고 포인터를 뒤로 이동시킨다. 그렇게 모든 요소를 순회한 후에 저장된 wIdx는 0이 아닌 수가 있었던 만큼 뒤로 밀려있다. 즉 wIdx 뒤로는 모두 0으로 채워 넣으면 된다.

private void copy(int[] nums) {
    int wIdx = 0;
    for (int idx = 0; idx < nums.length; idx++) {
        if (nums[idx] != 0) {
            nums[wIdx] = nums[idx];
            wIdx++;
        }
    }
    for (; wIdx < nums.length; wIdx++) {
        nums[wIdx] = 0;
    }
}