[LeetCode] 자바, 283. Move Zeroes

283. Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12] Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.

2. Minimize the total number of operations.

3.  

---

문제는 'int Array를 하나 주는데, 거기서 0을 모두 맨 뒤로 보내라' 입니다.

첫번째 시도는

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

버블정렬을 이용하는 방법입니다. 일반적으로 정렬을 오름차순, 또는 내림차순을 정렬하는데 사용하지만 알고리즘을 조금 비틀어서 하나씩 비교하면서 비교하는 수가 0일때 뒤로 보내는 방식입니다.

따라서 일반적인 버블정렬의 경우 이중for문 안의 if 문이 

if(nums[j]>nums[j+1])

인데 이 부분을 바꿔서 ==0일때만 숫자를 스위치해도록 바꿨습니다.

하지만 버블정렬 자체가 원체 시간이 많이 걸리는 정렬이라 정렬이 없이 하는 방법에 대해 생각해보겠습니다.

두번째시도.

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

크.. 실행시간이 다이나믹하게 줄어들었습니다. for문을 한번만 도는 O(n) 이기 때문에 이러한 결과가 나왔습니다.

두번째 시도의 아이디어는 배열을 하나씩 읽어가면서 0이 아닌경우 앞에서부터 하나씩 값을 넣는 방식입니다. 그리고 끝난 이후부터 마지막인덱스까지 0으로 채우는 것입니다.