[LeetCode] 283. Move Zeroes 해설 및 풀이 (Python)

LeetCode 283. Move Zeroes

https://leetcode.com/problems/move-zeroes/description/?envType=study-plan-v2&envId=leetcode-75

 

---

 

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

 

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:

Input: nums = [0]
Output: [0]
 

Constraints:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
 

Follow up: Could you minimize the total number of operations done?

 

한글 해석

 

정수 배열이 주어졌을 때 nums, 00이 아닌 요소의 상대적 순서를 유지하면서 모든 를 배열의 끝으로 이동합니다.

배열의 복사본을 만들지 않고 그 자리에서 이 작업을 수행해야 한다는 점에 유의하세요 .

 

예시 1:

입력: nums = [0,1,0,3,12]
 출력: [1,3,12,0,0]
예 2:

입력: nums = [0]
 출력: [0]
 

제약 조건:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
 

후속 조치: 총 작업 수를 최소화할 수 있나요?

---

문제 유형

Array

Two Pointers

 

풀이 방법 도출

 

주어진 배열에서 0이 아닌 원소의 상대적인 순서를 유지하면서 모든 0을 배열의 뒤쪽으로 이동시키는 문제입니다.

추가 조건으로 추가 배열을 쓰지 않고 원본 배열을 직접 수정해야 합니다.

 

따라서 투 포인터를 사용해서 이 문제를 해결할 수 있습니다.

 

fast는 배열을 탐색하며 0이 아닌 숫자를 찾습니다.

slow는 0이 아닌 숫자를 앞쪽부터 채워넣는 위치입니다.

 

fast가 배열 전체를 탐색하면서 0이 아닌 원소를 찾습니다.

그걸 slow 위치에 복사하고 slow를 증가시킵니다.

이렇게 0이 아닌 값이 모두 앞쪽으로 이동됩니다.

 

마지막으로 slow부터 배열 끝까지는 모두 0으로 채워주면 됩니다.

 

 

시간 복잡도

• O(N)

 

---

핵심 코드 삽입 및 설명

 

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # 투 포인터 초기화
        # slow는 0이 아닌 원소를 채울 위치
        # fast는 현재 탐색 중인 인덱스
        slow = 0
        fast = 0
        n = len(nums)
        
        # 0이 아닌 모든 원소를 앞쪽으로 이동
        while fast < n:
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        
        # 남은 부분은 모두 0으로 채움
        for i in range(slow, n):
            nums[i] = 0