리트코드 - 283. Move Zeroes

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

Move Zeroes - LeetCode

이 문제의 목표는 주어진 배열에서 모든 0을 배열의 끝으로 이동시키면서, 0이 아닌 요소들의 상대적인 순서를 유지하는 것이다. 이 작업은 "in-place"로 수행해야 하며, 배열의 복사본을 만들지 않아야 한다.

 

처음에 생각한 것은 버블정렬을 이용해서 정렬을 수행하는 풀이였다.

하지만 버블 정렬을 최적화해서 구현하더라도 해당 풀이는 시간 복잡도가 O(n^2)까지 발생한다.

 

그리고 문제를 보면 요소들은 이미 상대적인 순서들로 정렬되어 있고, 해당 순서를 유지시켜 주기만 하면 된다.

따라서 입력 리스트를 순회하기만 하면서 해당 요소들이 0이 아니라면 순서대로 리스트에 넣어주기만 하면 되고 

이후 정렬이 끝난 이후 남은 인덱스들의 부분을 0으로 채우면 된다.

 

이 과정은 모든 0이 아닌 요소를 배열의 앞쪽으로 이동시키고, 나머지 부분을 0으로 채워 배열을 "in-place"로 변경한다.

 

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        insertPos = 0
        for num in nums: # O(n)
            if num != 0: # O(1)
                nums[insertPos] = num # O(1)
                insertPos += 1
        
        while insertPos < len(nums): # O(n) 최악의 경우
            nums[insertPos] = 0 # O(1)
            insertPos += 1

 

전체 시간 복잡도는 O(n)입니다. 배열을 두 번 순회하긴 하지만, 각 순회는 선형 시간이므로 전체적인 복잡도는 여전히 O(n)이다.

공간 복잡도

"in-place"로 작업하기 때문에 추가 공간은 사용하지 않습니다. 공간 복잡도는 O(1).