[코딩연습] Move Zeroes 0을 뒤로 밀기

LeetCode 문제 중 난이도 Easy인 Move Zeroes이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

주어진 배열 nums의 모든 0 값들을 뒤쪽으로 이동시키면서 0이 아닌 값의 순서는 그대로 유지하는 함수를 작성해라.

* nums의 복사본인 새로운 배열을 생성하지 않고 nums배열에서 작업한다

* 전체 연산의 수를 최소화한다

첫번째 방법은 가장 처음으로 0이 나오는 값의 인덱스를 구한다. 그리고 0의 인덱스값 뒤에 오는 요소들 중 처음으로 나오는 0이 아닌 숫자를 0의 인덱스에 넣고 숫자가 있던 자리는 0으로 바꾼다. 배열의 값이 0인 인덱스들에 같은 행위를 반복한다.

class Solution {
    public void moveZeroes(int[] nums) {
        
        int indexOfZero=-1;
        
        //맨처음 0을 찾아서 index값 가져옴
        for(int i=0 ; i<nums.length ; i++){
            if(nums[i]==0){
                indexOfZero=i;
                break;
            }
        }
        
        //0이 없으면 그대로 리턴
        if(indexOfZero==-1) return;
        
        //0이 있는곳으로 뒤에서 0이 아닌수를 가져오고 index를 하나 늘린다(반복)
        for(int i=zeroIndex ; i<nums.length ; i++){
            if(nums[i]==0) continue;
                nums[indexOfZero]=nums[i];
                nums[i]=0;
                indexOfZero++;
        }
    }
}

시간복잡도는 O(n), 공간복잡도는 O(1)이다. 이 방법은 경우에 따라 불필요한 추가연산을 하게 되는 경우가 있다. 아래 예시를 보자.

만일 nums가 [1, 0, 2, 4, 5, 0]라고 가정해보자. 그럼 연산순서는 아래와 같을 것이다.

[1, 0, 2, 4, 5, 0] -> [1, 2, 0, 4, 5, 0] -> [1, 2, 4, 0, 5, 0] -> [1, 2, 4, 5, 0, 0]

nums[2]에 0을 넣었다가 다시 4로 바꾸고 nums[3]도 0을 넣었다가 다시 5로 바꾼다.

두번째 방법은 배열을 탐색하면서 0이 아닌 숫자들을 앞에서부터 순서대로 집어넣고 그 뒤를 0으로 채우는 것이다.

class Solution {
    public void moveZeroes(int[] nums) {
        
        int index=0;
        
        //0이 아닌 숫자를 찾아서 앞에서부터 하나씩 채운다
        for(int i=0 ; i<nums.length ; i++){
            if(nums[i]!=0){
                nums[index]=nums[i];
                index++;
            }
        }
        
        //index뒤를 전부 0으로 바꾼다
        while(index<nums.length){
            nums[index]=0;
            index++;
        }
    }
}

이렇게 하면 특정 위치의 값을 두번씩 바꾸는 일은 없겠지만 0의 갯수가 많을수록 0을 채워넣는 연산이 중복되는 경우가 생긴다(0을 또다시 0으로 채우는 경우). 이 방법도 동일하게 시간복잡도는 O(n), 공간복잡도는 O(1)이다.

문제출처 - https://leetcode.com/problems/move-zeroes/