[LeetCode] No.283 Move Zeroes

문제링크

LeetCode

문제

배열에 존재하는 원소들의 순서를 바꾸지 않고 모든 0을 맨 끝으로 이동시킨 결과 반환합니다.

해결

먼저, 0을 찾았을 때, 0과 오른쪽의 원소를 바꿔주면서 끝까지 이동시킬 경우, 배열의 사이즈가 N이라 하면 시간복잡도는 $O(logN*$ 0의 개수$)$입니다.

이 방법 이외에 $O(N)$에 해결할 수 있는 방법이 있습니다.

0이 아닌 숫자를 찾았을 경우, 배열을 왼쪽으로 당겨주는 방법입니다.

먼저, 위치할 바로 배열을 가리키는 인덱스를 2개 사용합니다.

1번 인덱스는 배열을 순회하면서 0이 아닌 숫자를 찾습니다.

0이 아닌 숫자를 찾으면, 2번인덱스에 위치한 값과 1번 인덱스의 값을 바꾸어주고 2번 인덱스를 오른쪽으로 이동시켜 줍니다.

1번 인덱스가 배열의 끝까지 이동하면서 이런 과정을 반복시켜 주면 원하는 결과를 얻을 수 있습니다.

코드

class Solution {
    public int[] moveZeroes(int[] nums) {
        
        int secondIdx = 0;
        for(int firstIdx = 0; firstIdx<nums.length; firstIdx++) {
            if(nums[firstIdx] != 0) {
                int tmp = nums[secondIdx];
                nums[secondIdx] = nums[firstIdx];
                nums[firstIdx]= tmp;
                secondIdx++;
            }
        }
        return nums;
    }
}