[LeetCode] - 1089. Duplicate Zeros

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Duplicate Zeros" 문제입니다.

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

 

문제 : 

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 <= 10^4
• 0 <= arr[i] <= 9

---

이 문제는 고정 길이 정수 배열 arr가 주어졌을 때, 배열 내의 0이 나타날 때마다 0을 한 번 더 복제하여 나머지 요소를 오른쪽으로 이동시키는 문제입니다.

단, 원래 배열의 길이를 초과하는 요소는 쓰지 않으며, 입력 배열을 직접 수정해야 하고, 반환 값은 없습니다.

 

class Solution {
    public void duplicateZeros(int[] arr) {
        List<Integer> arr2 = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                arr2.add(0);
                arr2.add(0); 
            } else {
                arr2.add(arr[i]);
            }
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr2.get(i);
        }
    }
}

 

이 코드는 주어진 배열 arr에서 0이 나타날 때마다 0을 한 번 더 복제하여 나머지 요소를 오른쪽으로 이동시키는 문제를 해결합니다. 이 코드는 ArrayList를 사용하여 임시로 요소를 저장한 후, 다시 원래 배열에 복사하는 방식으로 동작합니다.

1. 새로운 리스트 생성 (arr2) :
   • 배열 arr의 요소들을 임시로 저장할 ArrayList를 생성합니다.
2. 요소 복제 :
   • 원래 배열 arr을 순회하면서 각 요소를 arr2에 추가합니다.
   • 만약 현재 요소가 0이면, 0을 두 번 추가합니다.
3. 원래 배열 업데이트 :
   • arr2 리스트의 요소들을 원래 배열 arr에 복사합니다.
   • 배열 arr의 길이까지만 복사합니다.

• 시간 복잡도 : O(n)
  • 첫 번째 for 루프에서 arr의 모든 요소를 한 번 순회합니다. 이는 O(n) 시간이 걸립니다.
  • 두 번째 for 루프에서 arr2의 요소를 다시 arr에 복사합니다. 이는 O(n) 시간이 걸립니다.
  • 따라서 전체 시간 복잡도는 O(n) + O(n) = O(n)입니다.

• 공간 복잡도 : O(n)
  • ArrayList arr2를 사용하여 원래 배열의 요소를 임시로 저장합니다.
  • arr2의 크기는 최대 2 * n이 될 수 있지만, 실제로 배열 arr의 길이까지만 사용됩니다.
  • 따라서 공간 복잡도는 O(n)입니다.

---

제 코드도 나름 심플하다고 생각했지만 생각보다 Runtime 결과가 좋지 못해서 다른 유저들 중 효과가 좋았던 코드를 하나 찾아서 공유해드리려고 합니다.

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

        int[] temp = arr.clone();//for copy arr

        int ind = 0;

        for(int i=0; ind<n; i++){
            arr[ind++] = temp[i];
            if(temp[i] == 0 && ind != n) arr[ind++] = 0;
        }
    }
}
// omjethva24 유저의 코드

 

이 코드는 주어진 배열 arr에서 0을 복제하고 나머지 요소를 오른쪽으로 이동시키는 문제를 해결합니다. 이 코드는 임시 배열 temp를 사용하여 원래 배열 arr의 복사본을 만든 후, 이를 기반으로 원래 배열을 수정합니다.

1. 배열 복사 (temp 생성) :
   • 주어진 배열 arr을 clone() 메소드를 사용하여 복사합니다. 복사된 배열은 temp에 저장됩니다.
2. 인덱스 초기화 (ind) :
   • ind 변수는 새로운 배열에서 요소를 삽입할 위치를 추적합니다. 이를 0으로 초기화합니다.
3. 배열 순회 및 복제 :
   • temp 배열을 순회하면서 원래 배열 arr에 요소를 삽입합니다.
   • 만약 현재 요소가 0이면, 0을 한 번 더 복제합니다.
   • 복제 후, 인덱스 ind를 증가시킵니다.
   • 배열의 길이를 넘지 않도록 ind < n 조건을 사용합니다.

• 시간 복잡도 : O(n)
• 공간 복잡도: O(n) 로 보입니다

---

내 코드와 다른 유저 코드 Runtime 결과