Move Zeroes

Q: 다른 요소의 순서를 바꾸지 않고 0을 끝으로 어떻게 옮기나요?

앞쪽의 다음 빈 위치를 가리키는 write 인덱스를 유지하고, 두 번째 인덱스로 탐색하세요. 찾은 0이 아닌 각 값은 write 위치와 교환하고, write 는 오른쪽으로 한 칸 이동합니다. 값은 찾은 순서대로 배치되므로 상대적인 순서는 바뀌지 않습니다.

Q: 0 이동을 더 적은 쓰기 횟수로 할 수 있을까요?

맞습니다. 값을 서로 바꾸는 대신 0이 아닌 각 값을 nums[write] 에 복사하고, 탐색이 끝난 후 write 부터 끝까지 모든 위치를 0으로 채우세요. 이렇게 하면 각 위치에 최대 한 번만 씁니다. 또한 read 와 write 가 같으면 값을 이미 있는 위치에 다시 쓰게 되므로, 이때는 값 교환을 건너뛸 수도 있습니다.

쉬움투 포인터

+10

정수 배열 nums가 주어집니다. 모든 0을 배열의 끝으로 옮기고 나머지 값은 기존 순서대로 유지하세요. 재배열된 배열을 반환하세요. 이 배열의 길이는 nums와 같습니다.

함수

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: 재배열할 정수 배열
반환값integer-array: 0이 아닌 값은 원래 순서대로 앞에 두고, 모든 0은 끝에 둔 nums

제약 조건

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

예제

입력: nums = [0, 4, 0, 7, 2]
출력: [4, 7, 2, 0, 0]
설명: 0이 아닌 값은 4, 7, 2이며, 앞쪽에 원래 순서대로 유지됩니다. 두 개의 0은 마지막 두 자리를 채웁니다.

제출 시 숨은 테스트 +14개

후속 질문

대신 모든 0을 앞으로 옮기고 다른 값은 순서를 유지하면서, 추가 메모리 O(1)로 한 번에 처리할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

0을 끝으로 보내는 것은 어려운 부분이 아닙니다. 다른 값들을 원래 순서대로 유지하는 것이 어려운 부분이며, 따라서 각 0을 마지막 요소와 교환하는 방법은 사용할 수 없습니다. 배열을 지금까지 찾은 0이 아닌 값들을 담는 앞쪽 영역과 나머지 영역으로 나누세요. 하나의 인덱스는 모든 요소를 읽고, 두 번째 인덱스는 다음 0이 아닌 값이 들어갈 위치를 표시하며, 한 번만 순회하면 제자리에서 작업을 마칠 수 있습니다.

0이 아닌 값을 복사합니다

핵심 아이디어

새 배열을 만드세요. nums를 순회하며 0이 아닌 모든 값을 마주치는 순서대로 복사하세요. 그런 다음 새 배열의 길이가 nums와 같아질 때까지 0을 추가하세요. 추가하는 0의 개수는 건너뛴 값의 개수입니다.

[0, 4, 0, 7, 2]의 경우 복사 단계에서 [4, 7, 2]가 만들어지고, 0 두 개를 추가하면 [4, 7, 2, 0, 0]이 됩니다. 값을 읽는 순서대로 복사하므로 순서가 유지됩니다.

각 요소를 한 번 읽고 한 번 쓰므로 시간 복잡도는 O(n)입니다. 두 번째 배열은 O(n)의 메모리를 사용하며, 다음 접근법에서는 이를 피합니다.

알고리즘

빈 결과 배열을 만드세요.
nums의 각 값에 대해, 0이 아니면 결과에 추가하세요.
결과의 항목 수가 nums와 같아질 때까지 0을 추가하세요.
결과를 반환하세요.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

두 포인터, 제자리에서 교환하기

핵심 아이디어

두 개의 인덱스를 사용하세요. read는 왼쪽에서 오른쪽으로 모든 요소를 방문합니다. write는 다음 0이 아닌 값이 들어갈 위치를 표시합니다. 각 단계를 마친 뒤에는 두 가지 사실이 성립합니다. write 앞부분에는 지금까지 확인한 0이 아닌 값이 원래 순서대로 있고, write부터 read까지는 모두 0입니다.

nums[read]가 0이 아니면 nums[write]와 교환하고 write를 오른쪽으로 한 칸 이동합니다. read에 놓이는 값은 0 구역에 있던 0이거나, 두 인덱스가 같을 때는 같은 값입니다. 0이 아닌 값은 0만 뛰어넘고 서로는 뛰어넘지 않으므로 순서가 유지됩니다.

[0, 4, 0, 7, 2]에서 인덱스 1의 4를 인덱스 0과 교환하면 [4, 0, 0, 7, 2]가 됩니다. 인덱스 3의 7을 인덱스 1과 교환하면 [4, 7, 0, 0, 2]가 됩니다. 인덱스 4의 2를 인덱스 2와 교환하면 [4, 7, 2, 0, 0]가 됩니다. 한 번만 순회하고 두 번째 배열은 필요하지 않습니다. 시간 복잡도는 O(n), 메모리 복잡도는 O(1)입니다.

알고리즘

write를 0으로 설정합니다.
read를 첫 번째 인덱스에서 마지막 인덱스까지 이동합니다.
nums[read]가 0이 아니면 nums[read]와 nums[write]를 바꾼 다음, write에 1을 더합니다.
nums를 반환합니다.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

함정과 경계 사례

일반적인 버그는 다른 값의 순서를 깨뜨리거나 요소를 건너뜁니다.

각 0을 마지막 요소와 바꾸면 0은 이동하지만 나머지 순서는 뒤섞입니다. [0, 4, 7]은 [7, 4, 0]이 됩니다.
인덱스가 배열을 순회하는 동안 배열에서 0을 삭제하면 요소를 건너뜁니다. [0, 0, 5]에서 인덱스 0의 요소를 삭제하면 두 번째 0이 인덱스 0으로 이동하지만 루프는 인덱스 1로 넘어갑니다. 삭제할 때마다 배열의 나머지 요소도 이동하므로 루프의 시간 복잡도는 O(n²)입니다.
x > 0이 아니라 x != 0을 검사하세요. 음수는 0이 아닙니다. [-1, 0, -2]는 [-1, -2, 0]이 되어야 하지만, x > 0을 사용하면 복사 버전은 [0, 0, 0]을 반환합니다.
0이 없는 배열이나 0만 있는 배열은 변경되지 않은 채 반환되어야 합니다. 교환 버전에서는 첫 번째 0을 만날 때까지 read와 write가 같으므로, 이러한 교환은 아무것도 바꾸지 않습니다.
Lua와 R에서는 배열이 1부터 시작하므로 write도 1에서 시작합니다.

자주 묻는 질문4

Move Zeroes의 시간 복잡도는 얼마인가요?

O(n). 두 가지 접근 방식 모두 각 요소를 한 번씩 읽습니다. 0이 아닌 값을 새 배열에 복사하려면 O(n)의 추가 메모리가 필요하지만, 두 포인터 교환 방식은 O(1)의 추가 메모리만 사용해 배열 내부에서 작동합니다.

다른 요소의 순서를 바꾸지 않고 0을 끝으로 어떻게 옮기나요?

앞쪽의 다음 빈 위치를 가리키는 write 인덱스를 유지하고, 두 번째 인덱스로 탐색하세요. 찾은 0이 아닌 각 값은 write 위치와 교환하고, write는 오른쪽으로 한 칸 이동합니다. 값은 찾은 순서대로 배치되므로 상대적인 순서는 바뀌지 않습니다.

0 이동을 더 적은 쓰기 횟수로 할 수 있을까요?

맞습니다. 값을 서로 바꾸는 대신 0이 아닌 각 값을 nums[write]에 복사하고, 탐색이 끝난 후 write부터 끝까지 모든 위치를 0으로 채우세요. 이렇게 하면 각 위치에 최대 한 번만 씁니다. 또한 read와 write가 같으면 값을 이미 있는 위치에 다시 쓰게 되므로, 이때는 값 교환을 건너뛸 수도 있습니다.

Move Zeroes가 왜 투 포인터 문제인가요?

한 포인터는 모든 요소를 읽고 다른 포인터는 완성된 앞부분의 끝을 표시합니다. 두 포인터 모두 앞으로만 이동하므로 함께 한 번만 순회합니다. 같은 읽기 및 쓰기 패턴으로 정렬된 배열에서 중복을 제거하거나 배열에서 원하는 값을 제자리에서 필터링할 수 있습니다.

Python

def moveZeroes(nums):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

nums = [0, 4, 0, 7, 2]

기대값

[4, 7, 2, 0, 0]