LeetCode 풀기 - 283. Move Zeroes

283. Move Zeroes

https://leetcode.com/problems/move-zeroes/

Move Zeroes - LeetCode

문제)

솔루션1)

 

연산 수행 속도를 최소화하는 것이 follow up에 명시되어 있네요.

 

문제 자체는 쉬웠는데 속도가 너무 느리네요.

시간 복잡도가 O(n^2)입니다.

 

풀이 전략:

1) 배열에서 0에 해당하는 모든 인덱스를 검색

2) 0에 해당하는 요소의 마지막에 있는 것 부터 뒤로 swap하면서 옮겨간다.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        # zero 인덱스 찾기
        locate = lambda nums, target: [idx for idx, n in enumerate(nums) if n == target]
        zero_indices = locate(nums, 0)
        
        # 제일 뒤 부터 0을 배치하는 방식
        last_zero_index = len(nums) - 1
        for zero_index in reversed(zero_indices):
            for i in range(zero_index, last_zero_index):
                # swap
                nums[i], nums[i+1] = nums[i+1], nums[i]
            last_zero_index -= 1

솔루션2)

leetcode의 discuss를 보니 신박하게 풀었네요.

시간복잡도가 O(n), 공간복잡도 O(1)입니다.

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

솔루션3)

인터뷰에는 적합하지는 않지만 직관적이고 단순하게 아래와 같이도 풀 수 있습니다.

0의 수만큼 삭제를 수행하고 배열 뒤에 0를 추가합니다.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        zero_count = nums.count(0)
        for _ in range(zero_count):
            nums.remove(0)
            nums.append(0)