[LeetCode] 1089. Duplicate Zeros

- Problem

1089. Duplicate Zeros

문제에 대해 심플하게 얘기를 하자면,
arr 배열의 원소 중 0이 있다면 오른쪽에 0을 하나 더 놔둔 후, 밀려난 원소는 버리는 것이다.

- 내 풀이 1

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        i = 0
        N = len(arr)
        
        while i < N:
            if not arr[i]:
                arr.insert(i, 0)
                arr.pop()
                i += 1
            i += 1

결과

단순하고 비효율적인 풀이방법이다.
문제의 제약 조건을 보면, arr의 길이는 최대 10^4인 것을 볼 수 있다.
arr.insert(i, v) 함수는 arr 배열의 인덱스 i에 v라는 값을 추가하기 위해, 배열을 전부 비집고 들어가야 하니 시간 복잡도 O(n)이다. (생각해보니 insert후, 다시 재정렬도 해줘야 한다.)
만약, 배열의 길이가 더욱 커진다면 insert 함수를 쓰기에는 다소 어려울 것으로 보인다.

- 내 풀이 2

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        shift = arr.count(0)
        N = len(arr)
        
        for i in range(N-1, -1, -1):
            if i + shift < N:
                arr[i+shift] = arr[i]
            
            if arr[i] == 0:
                shift -= 1
                if i + shift < N:
                    arr[i+shift] = 0    
                

discuss를 참고했다.
시간 복잡도 O(N), 공간 복잡도 O(1)을 만족하는 최적의 풀이인 것 같다.

아니 이거 easy 맞냐고 easy 난이도 중엔 어려운 편에 속한 것 같다...(개인적인 의견)