2. duplicate Zeros

문제

arr에 0이 있으면 우측에 0을 추가하라. 추가 후 각 요소는 한 칸씩 옆으로 밀린다.

배열의 길이는 고정되어 있다고 가정한다.  

 

내가 해결한 방식 

- 공간 복잡도 O(n)

- 시간 복잡도는 O(n)

 

1) 새 요소를 저장할 배열 tmp 생성

2) arr를 탐색할 인덱스 i, tmp를 탐색할 인덱스 j 생성 

3) i로 arr를 한 번에 한 요소씩 탐색 

   - arr[i]가 0인 경우 : tmp[j]와 tmp[j+1]에 0 저장

      저장 후 i는 1만큼 앞으로, j는 2만큼 앞으로 가게 만듦

      (j+1이 인덱스 범위 내에 있어야 한다는 조건을 달아야 오류가 안 남)

   - arr[i]가 0이 아닌 경우 : tmp[j]에 arr[i] 값 저장

     저장 후 i와 j 둘 다 1만큼 앞으로 가게 만듦

4) 탐색 끝나면 arr에 tmp를 덮어씀

void duplicateZeros(int* arr, int arrSize){
    int i = 0;
    int j = 0;
    
    // 새 요소를 입력할 배열 준비
    int tmp[arrSize];
    
    // i는 입력된 arr 배열을, j는 tmp 배열을 탐색함
    while (i < arrSize && j < arrSize){
    	// j + 1이 배열 크기보다 작아야 한다는 조건이 있어야 마지막 요소가 0이라도 오류가 나지 않음
        // arr의 i인덱스가 0인 경우 tmp 배열의 j 인덱스와 j 다음 인덱스에 0을 저장
        // 저장 후 i는 1만큼, j는 2만큼 이동
        if (arr[i] == 0 && j+1 < arrSize){
            tmp[j] = 0;
            tmp[j+1] = 0;
            i++;
            j += 2;
        }
        // arr의 i인덱스가 0이 아닌 경우 tmp 배열의 j인덱스에 arr[i] 저장
        else {
            tmp[j] = arr[i];
            i++;
            j++;
        }
    }
	
    // 새 배열을 반환할 수 없다는 조건이 있으므로 tmp 배열의 내용을 arr 배열에 덮어씀
    for (int k = 0; k < arrSize; k++){
        arr[k] = tmp[k];
    }
}

 

다른 해결 방식

https://leetcode.com/problems/duplicate-zeros/discuss/322576/Python-3-real-in-place-solution

- 시간 복잡도 : O(n)
- 공간 복잡도 : O(1)

 

arr의 한 요소는 좌측에 있는 0의 개수만큼 우측으로 이동함.

0은 새로 추가된 0.

기존 arr = [1, 0, 2, 3, 0, 4, 0, 5]

변형 arr = [1, 0, 0, 2, 3, 0, 0, 4, 0, 0, 5]

최종 arr = [1, 0, 0, 2, 3, 0, 0, 4]

1은 좌측에 0이 총 0개 있음 => 0만큼 이동

2, 3은 좌측에 0이 총 1개 있음 => 1만큼 이동

4는 좌측에 0이 총 2개 있음 => 2만큼 이동

5는 좌측에 0이 총 3개 있음 => 3만큼 이동

 

1) 전체 0의 개수 구하기

2) 뒤로부터 앞으로 iterate:

    - 현재 요소를 우측으로 이동하기 : 현재 인덱스 + 앞선 0의 개수에 현재 요소 넣기. 

       (단, 이동할 인덱스가 arr 길이 내인 경우에만) 

    - 현재 요소가 0이면 우측으로 이동 후 좌측에 0 넣기. 총 0의 개수에서 1 빼기.

def duplicateZeros(arr):
  # 1) 전체 0의 개수 구하기
  zero_count = arr.count(0)
  
  # 2) 뒤로부터 앞으로 iterate
  for i in range(len(arr) - 1, -1, -1):
      if i + zero_count < len(arr):
          # 현재 요소를 우측으로 이동하기 : 현재 인덱스 + 앞선 0의 개수에 현재 요소 넣기. 
          arr[i + zero_count] = arr[i]
      # 현재 요소가 0이면 이동한 위치의 좌측에 0 넣기
      if arr[i] == 0:
          zero_count -= 1
          if i + zero_count < len(arr):
              arr[i + zero_count] = 0