[리트코드] 283. Move Zeroes

283. Move Zeroes

in place(나머지 숫자의 순서를 바꾸지 않고) 로 0을 오른쪽으로 옮기기

[0, 5, 0, 7, 6, 3]

0을 무조건 오른쪽으로 옮긴다면?

나머지 숫자를 한 칸씩 앞으로 옮겨야하므로 오퍼레이션이 복잡해짐

0을 버블 스왑한다면 ?

O(n * 0의 개수)로 시간 복잡도가 너무 커짐

basic Idea

0을 찾아서 옮긴다면 나머지 숫자들의 순서가 바뀌지 않아야 하므로 버블 스왑 할 수 밖에 없음

그렇다면 0이 아닌 숫자를 찾아서 왼쪽으로 옮긴다면? 숫자만 옮기면 되니까 순서가 바뀔 일이 없음

[0,0,0,0,5,9,3]
[5,0,0,0,0,9,3]
[5,9,0,0,0,0,3]
[5,9,3,0,0,0,0]

투포인터를 사용한다.

start : 0을 가리킴

end : 0이 아닌 숫자를 가리킴

1. end 포인터를 한 칸씩 움직이며 0이 아닌 숫자를 찾는다.
2. start에 있는 0과 스왑한다.
3. start를 오른쪽으로 한칸 옮긴다.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        z_idx = 0
        
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[z_idx], nums[i] = nums[i], nums[z_idx]
                z_idx += 1