[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) {
        int[] res = new int[arr.length];
        int j = 0;
        for(int i =0; i<res.length; i++) {
            if(arr[i] == 0) {
                if(res[j] < res.length -1)
                    break;
                res[j] = 0;
                j++;
                res[j++] = 0;
                j++;

            } else {
                if(res[j] < res.length -1)
                    break;
                res[j] = arr[i];
                j++;
            }
        }
    }
}

 

처음에는 아주 단순하게 문제를 생각했다. 이게 다 문제를 제대로 읽지 않아서 생긴 일이다. 하나의 배열을 새로 선언하고, 그 배열을 0 중복하게 해서 단순하게 배열 범위를 벗어나는 것을 해결했다. 그런데 leetcode에서 run을 하면 계속 답이 넣은 값과 똑같은 값이 출력 되는 것이다. 그래서 뭐가 문제인가 하고 봤더니 문제에도 fix arr 라고 적혀 있고 leetcode는 in-place 방식이라는 것을 알게 되었다. 백준이었다면 이 문제는 아주 간단하게 풀렸을 것이다. 하지만 리트코드는 그런 거 없었다. 그래서 새로운 알고리즘을 생각해내야했다.

class Solution {
    public void duplicateZeros(int[] arr) {
        int length = arr.length;

        int cnt = 0;
        for (int i = 0; i < length; i++) {
            if (arr[i] == 0) {
                cnt++;
            }
        }

        for (int i = length - 1; cnt > 0; i--) {
            int newIndex = i + cnt;
            if (newIndex < length) {
                arr[newIndex] = arr[i];
            }

            if (arr[i] == 0) {
                if (newIndex - 1 < length) {
                    arr[newIndex - 1] = arr[i];
                }
                cnt--;
            }
        }
    }
}

 

이 문제에서 결국 가장 중요한 건 배열 범위를 벗어나는 것을 처리하는 일이다. 0이 몇 개가 있는지 먼저 확인한다. int newIndex = i + cnt;  로 이동할 위치를 만들어주고,  arr[i] 가 0 이라면 arr[i + cnt] 에 0 을 넣고 인덱스를 앞으로 shift한다. 가장 중요한 건  i +cnt 가 배열의 길이보다 작아야 한다는 것이다. 

내 코드가 얼마나 비효율적인지 다시 한 번 깨달았다. 리트코드가 좋은 점은 내 코드가 다른 사람들에 비해 얼마나 runtime이 긴지 알 수 있다느 ㄴ것이다. 또한 미리 풀이를 볼 수 있다는 것이다. 결국 오늘도 풀이를 봐버렸다. 하지만 언젠가는 이 문제도 그냥 빨리 풀 수 있게 될 것이다.