[LeetCode] 1089. Duplicate Zeros, Easy

1. 문제

• 고정 배열 arr이 주어질 때, 요소 중 0이 나오면 바로 다음 요소에 복제하고, 기존 요소들은 1칸 씩 뒤로 밀려진 배열을 구성하라.
• 새로운 배열을 사용하지 말고, 처음 제공되는 arr 배열을 수정하라. 배열 반환 X.

2. 해결

/**
 Do not return anything, modify arr in-place instead.
 */
function duplicateZeros(arr: number[]): void {
    let index = 0;

    while(index <= arr.length-1) {
        if(arr[index] !== 0) {
            index++;
            continue;
        }

        if(index >= arr.length-2) {
            for(let i = index; i < arr.length; i++) {
                arr[i] = 0;
            }
        } else {
            for(let i = (arr.length - 2); i > index; i--) {
                arr[i+1] = arr[i]
                if(i === index+1) arr[i] = 0;
            }
        }
       
        index+=2;
    }
};

• 코딩 테스트가 싫었던 이유가 다시 떠오른 문제.
• 일단, 내 풀이는 배열을 탐색하면서 0인 요소를 만나면 그 다음 인덱스 요소부터 한 칸씩 미루는 방식을 적용했고, 마지막에서 두 번째 요소는 예외 적으로 0인 경우는 끝까지 0으로 채우는 방식을 사용했다.
• 근데, 이 방식 통과는 되는데 20ms 걸리더라. 최악의 경우 O(N^2)가 걸리는 거 같다.

function duplicateZeros(arr: number[]): void {
    let zeros = arr.filter(num => num === 0).length;
    let n = arr.length;

    // 뒤에서부터 역순으로 값 이동
    for (let i = n - 1; i >= 0; i--) {
        if (i + zeros < n) {
            arr[i + zeros] = arr[i];
        }

        // '0'일 경우 한 번 더 복제
        if (arr[i] === 0) {
            zeros--;
            if (i + zeros < n) {
                arr[i + zeros] = 0;
            }
        }
    }
}

• 이 방식은 배열 내 존재하는 0의 개수 만큼 배열이 확장되는 구조에서 착안한 방법. (0이 3개 존재하면, length 8인 배열은 length 11이 된다고 생각.)
• 탐색 포인터 i, 삽입 위치 포인터 i + zeros를 이용해서 탐색해 나간다.
• 예를 들어, 10230450인 경우 0은 3개.

i	zeros	i + zeros	element
7	3	10 (삽입 위치가 초과, zeros--)	0 - 그대로
6	2	8 (삽입 위치가 초과)	5 - 그대로
5	2	7 (삽입 가능)	4 (5번 인덱스 요소) -> 7번 인덱스 자리
4	2	6 (삽입 가능, zeros--)	0 (4번 인덱스 요소) -> 6번 인덱스 자리 추가 0 -> 5번 인덱스 자리
3	1	4 (삽입 가능)	3 (3번 인덱스 요소) -> 4번 인덱스 자리
2	1	3 (삽입 가능)	2 (2번 인덱스 요소) -> 3번 인덱스 자리
1	1	2 (삽입 가능)	0 (1번 인덱스 요소) -> 2번 인덱스 자리 추가 0 ->1번 인덱스 자리
0	0	0 (삽입 가능)	1 (0번 인덱스 요소) -> 0번 인덱스 자리

• 위 단계를 거쳐서 삽입이 된다. 근데 이걸 문제 보고 어떻게 떠올려? =_=
• 이 문제를 통해 배운건 배열을 탐색할 때 효율적으로 하기 위해선 투 포인터!!!!를 고려해보자.