파이썬으로 배열 속 0 중복하기 – 알고리즘 문제 풀이

문제 소개

정수로 구성된 고정 길이 배열이 있다고 가정해 보겠습니다. 배열에 등장하는 모든 0을 하나 더 복제하고, 그 뒤의 나머지 요소들은 오른쪽으로 밀어내야 하는 것이 이번 과제입니다.

여기서 주의할 점은, 원래 배열의 길이를 벗어나는 위치의 요소는 새로 기록되지 않는다는 것입니다. 즉, 배열 길이는 변하지 않으며 밀려난 요소들은 자연스럽게 사라집니다.

예를 들어 배열이 [1,0,2,3,0,4,5,0]이라면, 수정 후 결과는 [1,0,0,2,3,0,0,4]가 됩니다.

해결 접근 방식

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

원본 배열 arr을 별도의 배열 arr2에 복사한 뒤, 포인터 i와 j를 0으로 초기화합니다.
i가 arr의 길이보다 작은 동안 아래 과정을 반복합니다.
- arr2[j]가 0인 경우:
  - arr[i]에 0을 저장합니다.
  - i를 1 증가시킵니다.
  - 만약 i가 여전히 arr의 길이 미만이라면, arr[i]에 한 번 더 0을 저장합니다(0을 복제).
- arr2[j]가 0이 아니라면, arr[i]에 arr2[j] 값을 그대로 저장합니다.
- i와 j를 각각 1씩 증가시킵니다.

핵심 아이디어는 원본 배열을 복사해 두고, 원본(arr)에는 결과를 덮어쓰면서 진행하는 것입니다. 복사본(arr2)을 읽어가며 원본(arr)을 채우기 때문에, 이미 덮어써진 값의 영향을 받지 않고 안전하게 처리할 수 있습니다.

구현 예제

아래 파이썬 코드를 통해 실제 구현을 확인해 보겠습니다.

class Solution(object):
    def duplicateZeros(self, arr):
        arr2 = [i for i in arr]
        i = 0
        j = 0
        while i < len(arr):
            if not arr2[j]:
                arr[i] = 0
                i += 1
                if i < len(arr):
                    arr[i] = 0
            else:
                arr[i] = arr2[j]
            j += 1
            i += 1
        return arr

ob1 = Solution()
print(ob1.duplicateZeros([1,0,2,3,0,4,5,0]))

실행 결과 확인

입력

[1,0,2,3,0,4,5,0]

출력

[1,0,0,2,3,0,0,4]

복잡도 분석

시간 복잡도: O(n) — 배열의 각 요소를 한 번씩만 순회합니다.
공간 복잡도: O(n) — 원본 배열의 복사본 arr2를 추가로 사용합니다.

이처럼 배열 복사본을 활용하면 인덱스 충돌 없이 간단명료하게 0 중복 문제를 해결할 수 있습니다.