[LeetCode][Easy] Move Zeroes 문제 Python 풀이

멍청한 풀이: 시간복잡도 O(n^2)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 1; j = 0; zeros = 0; moved = 0
        while i >= 0:
            if nums[i] != 0:
                zeros += 1
                i -= 1
            else:
                if zeros == 0: # if there's 0 at the end of the array, skip.
                    i -= 1
                    continue
                for j in range(zeros):
                    nums[i+j] = nums[i+j+1]

                nums[i+j+1] = 0
                zeros = 0
                moved += 1
                i = len(nums) - moved - 1

 

O(n)으로 개선하였으나 for-loop를 2번 사용하는 풀이:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        zeros = 0; i = 0; j = 0; size = len(nums)
        while i < size:
            if nums[i] == 0:
                zeros += 1
            else:
                nums[j] = nums[i]
                j += 1
            i += 1
        for ind in range(zeros):
            nums[size - ind - 1] = 0

 

변수 사용 최소화는 물론 for-loop 역시 단 한번만 써서 문제를 해결하는 풀이 (시간복잡도는 역시 O(n)):

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                # if i != j:
                tmp = nums[i]; nums[i] = 0; nums[j] = tmp
                j += 1