[leetcode] week1 - Move Zeroes

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3286/

 

0을 모두 배열의 끝으로 옮기는 것으로 연산을 최대한 줄이는 것이 목표다.

 

풀이

- p라는 포인터를 설정해서 0이 아닌 숫자를 만날 때까지 멈춰있다가 0을 만나면 1씩 증가한다.

1. 배열을 처음부터 끝까지 탐색한다.

2. 0을 찾으면 0을 지우고 0을 배열 맨 뒤에 더한다.

3. 0이 아니면 p를 1증가한다.

 

코드

del은 O(n)이고 if는 0의 개수(n-p)니까 O(n(n-p))

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        p = 0
        end = len(nums)
        while i < end:
            if nums[p] == 0:
                del nums[p:p+1]
                nums += [0]
            else:
                p+=1
            i += 1