[LeetCode] Java - Move Zeroes

 

LeetCode 30 Day Challenge 4일차 입니다.

문제 이름은 Move Zeroes

 

- 문제 

 

문제는 숫자 배열이 주어지고 in-place로 옮겨야 합니다.

함수를 call by reference 로 해결해야 한다는 의미 입니다.

주어진 변수 nums안의 데이터를 옮겨 해결한다는 의미 입니다.

 

- 풀이

class Solution {
    public void moveZeroes(int[] nums) {
    	
    	int temp = 0, zeroCount = 0;
    	if(nums[0] == 0) zeroCount++;
    	
    	for(int i=1; i<nums.length; i++) {
    		if(nums[i] == 0) {
    			zeroCount++;
    			continue;
    		}
    		if(nums[i-zeroCount] == 0) {
    			temp = nums[i];
    			nums[i] = nums[i-zeroCount];
    			nums[i-zeroCount] = temp;
    		}
    	}
    }
}

위 풀이 방법은 시간복잡도 O(n) 입니다.

 

임시로 수개의 숫자의 위치를 변경해줄 temp 변수와 현재까지 zero인 숫자를 카운트 하는 zeroCount 변수가 필요합니다.

만약 num[i]가 zero면 zeroCount를 증가 시키고 아니라면 num[i - zeroCount]의 숫자가 0이라면 현재 index의 값과 교체합니다.

이렇게 하면 0이 1개 이상이여도 한번의 교체만으로 문제를 해결 할 수 있습니다.

 

이해를 쉽게 돕자면 아래와 같이 변경되는 것을 알 수 있습니다.

 

[ 1, 0, 0, 3, 7 ] 

 

위 숫자일때 만약 index가 3이라면 3의 숫자를 바라보고 있고 현재 zeroCount는 2입니다.

그러면 nums[index-zeroCount]로 nums[3-2]의 값을 확인하고 0이기 때문에 현재 3과 위치를 변경합니다.

 

[1, 3, 0, 0, 7] 

 

그러면 위 배열처럼 변경이 되겠죠. 

한번의 교체만으로 우리가 원하는 값을 얻을 수 있습니다.

이렇게 O(n) 으로 문제를 해결할 수 있습니다.