.leetcode(1089. Duplicate Zeros)

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

 

1. 2022.04.16 시도

소요시간: 4분

class Solution {
    public void duplicateZeros(int[] arr) {
        for (int i=arr.length-1; i>=0; i--) {
            if ( arr[i] == 0) {
                for (int j=arr.length-2; j>=i; j--) {
                    arr[j+1] = arr[j];
                }
            }
        }   
    }
}

풀이 접근 과정

뒤에서부터 접근하면 더 편리하게 0의 배열을 관리할 수 있다.

0을 발견할 때, 그전껄 하나씩 쉬프트하는 방식으로 구현하였다.

 

느낀점

• 내가 푼 풀이보다 훨신 좋은 풀이가 있어서 소개한다. O(n)의 시간복잡도로 풀 수 있다.
  • 원리는 0의 갯수를 세서 실제로 마지막에 끝날 인덱스를 먼저 찾아낸다.
  • 그 후에 다시 배열을 읽으면서 0을 채워주는 로직이다.
  • 하나의 함정은 공간이 1개만 남았을 때, 0이 나온 상황이다. 마지막 0인 경우 duplicateZero를 만들었을 때, 잘리는 경우가 발생한다. 그때는 0을 두개로 계산하지 않고 1개로 계산해야한다.
    • ex) [1,0,0,0,2,3] => [1,0,0,0,0,0]
    • 여기서보면 0은 3개닌깐 복제하면 6개를 만들어야 할 것 같지만 실제로 공간상에는 5개만 존재할 수 밖에 없다.
    • 이걸 처리하기 위한 로직이 추가로 들어간다.

class Solution {
    public void duplicateZeros(int[] arr) {
        int counter=0;
        boolean isLastZero = false;
        for (int i=0; i<arr.length-counter; i++) {
            if ( arr[i] == 0) {
                if (i == arr.length-counter-1) {
                    isLastZero = true;
                    break;
                }
                counter++;
            }
        }
        
        for (int i=arr.length-1-counter; i>=0; i--) {
            if (isLastZero) {
                isLastZero = false;
                arr[i+counter] = 0;
                continue;
            }

            if (counter == 0) {
                break;
            }

            arr[i+counter] = arr[i];
            if (arr[i] == 0) {
                counter--;
                arr[i+counter] = arr[i];
            }
        }
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형