283. Move Zeroes

문제

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

풀이

1. 처음 풀이(새로운 배열, 오답)

class Solution {
    public int[] moveZeroes(int[] nums) {
        int index = 0;
        int[] answer = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != 0) {
                answer[index] = nums[i];
                index++;
            }
        }
        return answer;
    }
}

• 0을 만났을 때, 배열을 한칸씩 앞으로 당기고 0을 뒤로 위치하면 너무 비효율적인 방식같음
• 빈 배열을 하나 더 만들고, 0이 아닐 때만 이 배열에 추가해준다면, 뒤의 배열은 초기화된 값이므로 자연스레 0
  -> 공간 복잡도는 O(N)으로 생기겠지만, 훨씬 효율적인 방식으로 풀 수 있다.
• 라고 생각했지만, 해당 문제는 nums 배열을 in-place 방식으로 수정해야함.

=> in-place 수정으로 풀어보자!

2. 다른 풀이(in-place 수정, two pointers)

class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != 0) {
                nums[index] = nums[i];
                index++;
            }
        }
        
        for(int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

• 윗 풀이에서 어떻게 하면 in-place 방식으로 수정할 수 있을까?
  • 어차피 0이 아닌 경우에는 앞의 0들을 싹 다 무시하고 순서대로 위치하면 됨
  • index라는 별도의 포인터를 두고, 0이 아닌 경우에 nums[index]를 해당 숫자로 변환 후 index++;
  • 배열을 한 번 더 돌면, 0이 아닌 숫자들이 전부 앞으로 오게 됨
  • index 이후의 배열 숫자들을 0으로 변환해주면 끝!
    
• in-place 수정이라 별도의 공간복잡도도 없고, 시간 복잡도 또한 O(N)으로 이게 더 좋은 풀이!