1. Problem Description

Summary
배열에서 0을 발견하면 중복 삽입하고 이후 요소들은 오른쪽으로 밀어낸다.
요소의 이동이 핵심인 문제입니다.

example

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Constraints

1 <= arr.length <= 104
0 <= arr[i] <= 9

2. Approach to the Problem

• 먼저 주어진 배열에서 중복 될 0의 개수를 센다. 각 요소가 이동할 수 있는 거리(shift) 를 결정하는 역할을 한다.
• 배열의 끝에서부터 이동하면서 0을 삽입한다.

3. Code and Explanation

중복 될 0의 개수

possible_dups = 0
length_ = len(arr) - 1

for left in range(length_ + 1):
	
    if left > length_ - possible_dups:
    	break
                
    if arr[left] == 0:
    	if left == length_ - possible_dups:
        	arr[length_] = 0
            length_ -= 1
            	break
        else:
            possible_dups += 1

• length_ : 배열의 마지막 인덱스를 저장하는 변수
• possible_dups : 중복 될 0의 개수, 각 요소가 이동할 수 있는 거리(shift)

if left > length_ - possible_dups:

• 배열의 크기를 초과하는 요소를 방지한다.
• left : 현재 index
• length_ - possible_dups : 배열에서 중복 삽입을 고려한 최종 유지될 수 있는 마지막 요소 위치
• left가 length_ - possible_dups를 초과하면 배열 크기를 초과하기 때문에 더 이상 확인하지 않음

if arr[left] == 0:

• 현재 위치의 요소가 0인 경우

if left == length_ - possible_dups:

• 현재 위치가 마지막으로 0을 중복시킬 수 있는 위치인지 확인
• 현재 탐색중인 요소가 0이면 possible_dups를 증가시키고 중복에 대한 처리를 고려

arr[length_] = 0 와 length_ -= 1

• 마지막으로 추가할 수 있는 0을 배열 끝에 추가
• 배열 크기를 넘지 않도록 조정
• 이후 뒤에서부터 값을 이동하는 과정에서 배열이 초과되지 않게 함
• 마지막 위치에 0을 추가하고나서 마지막 위치를 갱신

배열의 끝에서부터 0을 삽입

배열에서 0을 발견하면 이를 중복삽입한다.

last = length_ - possible_dups

        # Copy zero twice, and non zero once.
        for i in range(last, -1, -1):
            if arr[i] == 0:
                arr[i + possible_dups] = 0
                possible_dups -= 1
                arr[i + possible_dups] = 0
            else:
                arr[i + possible_dups] = arr[i]

for i in range(last, -1, -1):

• last부터 시작하여 배열의 처음(인덱스 0)까지 역순으로 순회
• 0을 중복 삽입할 때 기존 요소들을 덮어쓰지 않도록 하기 위함
• 기존 요소가 덮어써지면 중복된 0이 사라질 수 있음
• i = 5, 4, 3, 2, 1, 0 순으로 실행

if arr[i] == 0:

• 현재 요소가 0이면, 이를 중복 삽입

arr[i + possible_dups] = 0

• 현재 위치에서 possible_dups만큼 오른쪽 위치에 0을 추가

possible_dups -= 1

• 중복할 0의 개수 감소

arr[i + possible_dups] = 0

• 현재 위치에서 갱신 된 possible_dups를 더한 위치에 0추가

else:

• 현재 요소가 0이 아니라면, 단순히 현재 요소를 가능한 오른쪽 위치로 이동

arr[i + possible_dups] = arr[i]

• 0이 아닌 경우는 단순히 이동만 수행하고, 중복 삽입은 하지 않음

4. Time and Space Complexity Analysis

Time Complexity

• O(N)

Space Complexity

• O(1)
• 배열을 새로 만들지 않음으로 O(1) 공간만 사용.

5. Alternative Approaches

초보자용 코드

from typing import List

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        new_arr = []  # 새로운 리스트를 만들어서 0을 중복 삽입할 공간 확보

        for num in arr:  # 배열의 요소를 하나씩 확인
            new_arr.append(num)  # 원래 숫자 추가
            if num == 0:  # 만약 0이면 한 번 더 추가
                new_arr.append(0)
            
            # 배열 크기를 초과하지 않도록 제한
            if len(new_arr) >= len(arr):
                break

        # 원래 배열에 복사 (in-place로 유지)
        for i in range(len(arr)):
            arr[i] = new_arr[i]

6. Improvements

• 배열 크기를 초과하지 않도록 제한하는 것이 중요하다.
  • 0을 중복 삽입할 때, 배열 크기를 유지하면서 수정하는 것이 핵심이다.
  • left > length_ - possible_dups 조건이 이를 보장한다.
• 변수를 나누어 역할을 설정하는 것이 생소할 수 있다.
  • possible_dups(중복할 0 개수)와 last(마지막 가능한 위치) 같은 변수를 미리 계산해야 한다.
  • 초보자는 한 번에 직접 구현하기 어려울 수 있으며, 차근차근 단계를 나누는 것이 중요하다.
• 배열을 앞에서부터 수정하지 않고 뒤에서부터 수정하는 패턴을 익히는 것이 중요하다.

7. Conclusion

• 이 문제는 배열을 직접 수정하면서 크기를 유지하는 패턴을 익히기에 좋은 문제다.
• 초보자는 먼저 새로운 배열을 사용해서 풀어본 뒤, 최적화된 O(1) 공간 복잡도의 해결 방법을 학습하는 것이 좋다.
• 0을 중복 삽입할 때, 배열을 뒤에서부터 수정하는 방식이 필요함을 이해하는 것이 중요하다.
• 배열의 크기를 유지하면서 요소를 조작하는 In-place 수정 기법을 연습할 수 있다.