[LeetCode] Duplicate Zeros

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

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]

---

Example 2:

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

---

Constraints:

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

---

✍풀이

class Solution {
    public void duplicateZeros(int[] arr) {
        for(int i = 0; i < arr.length; i++){
            if(arr[i] == 0){
            // 0을 발견하면
            // 배열의 끝에서부터 현재 위치까지 요소를 오른쪽으로 한 칸씩 이동
                for(int j = arr.length - 1; j > i; j--){
                    arr[j] = arr[j - 1];
                }
                i++; // 복제된 0을 건너뛰기 위해 인덱스를 증가
            }
        }
    }
}
}

작동 방식

• 0의 발견: 배열을 처음부터 끝까지 순회하며 0을 찾습니다.

• 배열 요소 이동: 0을 발견하면, 배열의 끝에서부터 현재 위치까지 모든 요소를 오른쪽으로 한 칸씩 이동합니다. 이는 복제된 0을 추가하기 위한 공간을 만듭니다.

• 0 복제: 0을 복제한 후, 다음 0을 건너뛰기 위해 인덱스 i를 한 칸 더 증가시킵니다.

코드의 문제점 및 개선 가능성
이 방법은 간단하지만, 중복 0을 처리할 때마다 배열 요소를 모두 한 칸씩 이동해야 하므로, 최악의 경우 시간 복잡도는 O(N^2)입니다. 배열의 크기가 크면 비효율적일 수 있습니다.

---

더 효율적인 방법은 두 번의 패스를 사용하는 것입니다. 첫 번째 패스에서는 배열을 순회하며 복제된 0이 포함된 배열의 크기를 계산하고, 두 번째 패스에서는 실제로 0을 복제하며 배열을 뒤에서부터 채워나갑니다. 이를 통해 시간 복잡도를 O(N)으로 줄일 수 있습니다.

class Solution {
    public void duplicateZeros(int[] arr) {
        int zeros = 0;
        int length = arr.length - 1;
        
        // 첫 번째 패스: 복제될 0이 포함된 배열의 크기 계산
        for(int i = 0; i <= length - zeros; i++) { 
            if(arr[i] == 0) {
                // 끝에서 0을 복제하는 경우를 고려하여 크기 조정
                if(i == length - zeros) {
                    arr[length] = 0;    // 마지막 위치에 0을 복제
                    length--;           // 배열의 크기를 하나 줄임
                    break;              // 0의 개수 추가 되는 것 방지
                }
                zeros++;    //0의 개수 증가
            }
        }
        
        // 두 번째 패스: 뒤에서부터 배열 채우기
        for(int j = length - zeros; j >= 0; j--){
            if(arr[j] == 0){
                arr[j + zeros] = 0; // 첫 번째 0 복제
                zeros--;
                arr[j + zeros] = 0; // 두 번째 0 복제
            }else{
                arr[j + zeros] = arr[j];    // 일반 요소 이동
            }
        }
    }
}

작동 방식

• 첫 번째 패스 (0의 개수 계산):
  배열을 처음부터 순회하며, 배열 내에서 0이 등장하는 횟수를 세어 zeros 변수에 저장합니다.
  만약 배열의 끝에 0이 있을 경우, 이를 복제할 공간이 있는지 확인하고, 마지막 위치에 0을 추가하고 종료합니다.

• 두 번째 패스 (배열 재구성):
  배열을 뒤에서부터 순회하며, 현재 요소가 0인 경우, 0을 두 번 복제하고, 그렇지 않은 경우에는 해당 요소를 그대로 이동시킵니다.
  이 과정을 통해 배열 내에서 0이 복제되며, 복제된 결과는 배열 내에서 적절하게 반영됩니다.

• 이 개선된 접근 방법은 배열을 한 번만 이동시키기 때문에 훨씬 효율적입니다.