1089. Duplicate Zeros

링크: https://leetcode.com/problems/duplicate-zeros/

Duplicate Zeros - LeetCode

 

 arr에 0이 있으면 2개로 늘리는데, inplace가 제한조건이다.

 

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int zeroCnt = 0;
        
        int right = arr.size() - 1;
        
        for(int i = 0; i < arr.size() - zeroCnt; i++){
            if(arr[i] == 0){
                if(i == arr.size() - zeroCnt - 1){
                    arr[right--] = 0;
                    continue;
                }
                zeroCnt++;
            }
        }
        
        int left = right - zeroCnt;
        
        while(left <= right && left >= 0){
            if(arr[left] == 0){
                arr[right--] = 0;
                arr[right--] = 0;
                left--;
            } else {
                arr[right--] = arr[left--];
            }
        }
    }
};

 0을 먼저 카운트하고, 0이 두 개로 늘어나는데 2개로 늘어날 때 2개중 하나가 arr의 길이를 벗어나는 경우를 체크해주는게 핵심이다.  이후에는 투 포인터로 left에 0이 나올때 right를 2개 줄이고, 0이 아닌 값이 나오는 경우 하나만 줄이면 inplace로 해결할 수 있다.

 

 키포인트는 [1, 2, 0, 0, 0, 7], [1, 2, 3, 0, 0, 0, 0, 8] 두 가지 케이스를 필터 가능한지 여부다.

 for(int i = 0; i < arr.size() - zeroCnt; i++) -> 이런식으로 조건을 주면 첫 번째 테스트 케이스에서 [1, 2, 0, 0]까지 돌고 멈추게된다.  0이 두 개가 나왔기에 뒤에 있는 [0, 7]은 생략되기 때문이다.  실제로 0이 2개로 복제되면 [0, 7]은 필요가 없어진다.  

 두 번째 케이스의 경우 [1, 2, 3, 0, 0, 0]까지 돌게된다.  그런데 마지막 값이 0이 들어오므로 아귀가 맞지 않다.  즉, 0이 들어오면 2개로 복제되어야하는데 복제될 자리는 [0, 8] 밖에 없고 이미 이전 0이 두 개가 있었으므로 맨 마지막에 위치한 0의 자리는 없다.  그래서 필터를 하지 않고 수행하면 [1, 1, 2, 3, 0, 0, 0, 0]과 같은 아웃풋이 출력된다.  맨 마지막 0의 zeroCnt가 반영되어 한 칸 밀려서 출력된 것이다.

 이에 맨마지막에 0이 들어오고 0 이후에 복제될 공간이 없다면 필터해주는거까지 고려해야 정확한 답을 낼 수 있다.