[LeetCode/EASY] 283. MoveZeroes (JAVA) : 문제&풀이

 

 

새로운 자료구조를 생성하지 않고,

주어진 int배열에서 0을 배열의 뒤로 모두 옮기는 문제이다.

e.g. {0, 3, 4, 0, 1, 0} -> {3, 4, 1, 0, 0, 0}

 

int 배열을 매개변수로 받는 moveZeroes 메서드의 틀이 주어진다.

 

Problem : 

public class MoveZeroes {
    public void moveZeroes(int[] nums) {
        
    }
}

풀이는 주어진 moveZeros 메서드에 작성하면 된다.

 

Solution :

1. 0이 아닌 숫자를 앞에서부터 채운다.
2. 0이 아닌 숫자를 채운 마지막 index를 기억한다.
3. 해당 index부터 배열 끝까지 0으로 채운다.

public class MoveZeroes {

    // time complexity : loop for int[] nums -> O(n)
    // space complexity : no additional space allocated -> O(1)
    public void moveZeroes(int[] nums) {
        // get non-zero digits
        int idx = 0;
        for (int num : nums){
            if(num != 0) nums[idx++] = num;
        }

        // fill with zeroes
        while (idx < nums.length){
            nums[idx++] = 0;
        }
    }
}

 

Complexity :

• 시간복잡도 (Time Complexity)
  • 주어진 배열 길이만큼 반복함에 따라 O(n)
• 공간복잡도 (Space Complexity)
  • 추가로 할당한 공간이 없으므로 O(1)

 

Sample(Test) :

import java.util.Arrays;

public class MoveZeroes {

    // time complexity : loop for int[] nums -> O(n)
    // space complexity : no additional space allocated -> O(1)
    public void moveZeroes(int[] nums) {
    
        // get non-zero digits
        int idx = 0;
        for (int num : nums){
            if(num != 0) nums[idx++] = num;
        }

        // fill with zeroes
        while (idx < nums.length){
            nums[idx++] = 0;
        }

        System.out.println(Arrays.toString(nums));
    }

    public static void main(String[] args) {
        int[] nums = {0, 3, 4, 0, 1, 0};

        MoveZeroes m = new MoveZeroes();
        m.moveZeroes(nums);
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

[3, 4, 1, 0, 0, 0]