283. Move Zeroes

0을 맨 뒤로 이동시키는 문제다.

Solution

1. 0이 아닌 숫자를 앞으로 이동시키면서 수를 센다.
2. 0이 아닌 숫자의 갯수를 시작할 인덱스로 두면 나머지가 된다. 나머지는 0으로 변경한다.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        cnt = 0 # 0이 아닌 수 세기
        l = len(nums)

        for i in range(l): # 0이 아닌 숫자 앞으로 이동
            if nums[i] != 0:
                nums[cnt] = nums[i]
                cnt += 1

        for i in range(cnt, l): # 나머지에 0 삽입
            nums[i] = 0
        

시간 복잡도

1. 리스트의 길이만큼 반복문이 실행되므로 O(n)
2. 나머지 배열을 변경하므로 최악의 경우 O(n)

전체적으로 시간 복잡도는 O(n)이다.