LeetCode 283(Move Zeroes, java)

0. 문제

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

Move Zeroes - LeetCode

 

1. 문제 설명

- 문제에서 정수형 배열(nums)이 주어진다.

- 배열의 원소 중 0인 원소를 배열의 가장 마지막 위치부터 채운다.

- 0을 제외한 나머지 원소들은 오름차순으로 정렬하여 배열의 첫 번째 위치부터 채운다.

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제는 버블 정렬을 사용하면 쉽게 풀 수 있다.

- 어떤 원소가 0인 경우, 0이 아닌 다음 원소를 찾아서 해당 원소와 swap한다.

- 즉, 2개의 포인터를 사용하여 swap하는 방식이다.

 

- 그러나 버블 정렬은 효율적인 시간 복잡도를 가지지 않는다.

- 그러므로 다른 접근 방법을 생각해야한다.

 

b) 두 번째 접근

- 정렬을 두 번 수행하는 방법을 사용할 수 있다.

 

- 첫 번째 정렬에서 for 반복문으로 배열(nums)을 탐색한다.

- 0이 아닌 원소가 등장하면 해당 원소를 배열(nums)의 좌측부터 순차적으로 저장한다.

- 이때 배열(nums)의 좌측부터 순차적으로 원소를 저장하기 위해 포인터를 사용한다. 

- 즉, 0을 무시하고 0이 아닌 원소만을 배열(nums)의 좌측부터 순차적으로 정렬한다.

 

- 두 번째 정렬 또한 for 반복문으로 배열(nums)을 탐색한다.

- 첫 번째 정렬이 종료되면 0이 아닌 원소는 모두 배열(nums)의 좌측에 순차적으로 정렬되어있다.

- 그리고 포인터는 가장 마지막에 저장된 원소의 다음 위치를 가리킨다.

- 포인터가 가리키는 위치부터 배열의 끝까지 0을 삽입하면 된다.

 

- 설명이 어렵다.

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

a) 버블 정렬 응용 

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length < 2) return;
        
        int left = 0;
        int right = 1;
        
        while(right < nums.length) {
            if(nums[left] == 0) {
                if(nums[right] != 0) {
                    nums[left] = nums[right];
                    nums[right] = 0;
                    left++;
                    right++;
                }
                else {right++;}
            } else {
                left++;
                if(left == right) {
                    right++;
                }
            }
        }
    }
}

 

b) 두번 정렬하는 방법

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