[LeetCode 75] Easy - 283. Move Zeroes ☆

283. Move Zeroes

 

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 <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

 

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

 

문제 풀이

이 문제는 배열 nums에서 모든 0을 배열의 끝으로 이동시키는 문제입니다. 0이 아닌 숫자들의 상대적인 순서는 그대로 유지해야 하며, 배열을 제자리에서(in-place) 수정해야 합니다. 새로운 배열을 생성하지 않고 작업을 수행해야 하므로 추가 메모리 사용을 최소화해야 합니다.

---

문제 조건

1. 입력: 정수 배열 nums
   • 배열의 크기: 1 ≤ nums.length ≤ 10^4
   • 배열 요소 값: −2^31 ≤ nums[i] ≤ 2^31−1
2. 출력:
   • 0이 배열의 끝으로 이동한 후 수정된 배열.
3. 제약 조건:
   • 배열을 직접 수정해야 하며, 추가 배열을 사용할 수 없습니다.
   • 0이 아닌 숫자의 상대적인 순서는 유지해야 합니다.
4. 목표:
   • 연산 수를 최소화하여 해결.

풀이 전략

1. 두 포인터 접근법

• 배열을 한 번 순회하면서 0이 아닌 숫자를 앞으로 이동하고, 0은 뒤에 남도록 처리합니다.
• 포인터의 역할:
  • i: 현재 요소를 검사하는 포인터.
  • last_non_zero: 0이 아닌 요소를 저장할 위치를 가리키는 포인터.
• 각 요소를 순회하면서:
  • 0이 아닌 경우, last_non_zero 위치에 숫자를 이동하고, last_non_zero를 증가시킵니다.
  • 최종적으로 last_non_zero 이후에 남은 자리를 모두 0으로 채웁니다.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # 0이 아닌 숫자를 저장할 위치를 나타내는 포인터
        last_non_zero = 0

        # 첫 번째 루프: 배열을 순회하며 0이 아닌 숫자를 앞으로 이동
        for i in range(len(nums)):
            if nums[i] != 0:  # 현재 숫자가 0이 아니면
                nums[last_non_zero] = nums[i]  # last_non_zero 위치에 저장
                last_non_zero += 1  # 다음 저장 위치로 포인터 이동

            # 현재 상태를 주석으로 표시:
            # 예제 1: nums = [0, 1, 0, 3, 12]
            # i = 0 -> nums[0] == 0 -> 아무 작업 안 함, last_non_zero = 0
            # i = 1 -> nums[1] == 1 -> nums[0] = 1, last_non_zero = 1
            # i = 2 -> nums[2] == 0 -> 아무 작업 안 함, last_non_zero = 1
            # i = 3 -> nums[3] == 3 -> nums[1] = 3, last_non_zero = 2
            # i = 4 -> nums[4] == 12 -> nums[2] = 12, last_non_zero = 3
            # 중간 결과: nums = [1, 3, 12, 3, 12], last_non_zero = 3

        # 두 번째 루프: 나머지 위치를 모두 0으로 채움
        for i in range(last_non_zero, len(nums)):
            nums[i] = 0  # 남은 공간을 0으로 설정

            # 현재 상태를 주석으로 표시:
            # 예제 1: nums = [1, 3, 12, 3, 12], last_non_zero = 3
            # i = 3 -> nums[3] = 0 -> nums = [1, 3, 12, 0, 12]
            # i = 4 -> nums[4] = 0 -> nums = [1, 3, 12, 0, 0]
            # 최종 결과: nums = [1, 3, 12, 0, 0]

첫번째 솔루션인 GPT 코드가 제일 이해하기 쉬움!!

시간 및 공간 복잡도

1. 시간 복잡도:
   • 첫 번째 루프: O(n) (배열을 한 번 순회).
   • 두 번째 루프: O(n) (배열을 한 번 순회).
   • 전체: O(n).
2. 공간 복잡도:
   • 추가 배열을 사용하지 않으므로 O(1).

 

요약

1. 핵심 아이디어:
   • 두 포인터를 사용하여 0이 아닌 숫자를 앞으로 이동.
   • 남은 공간을 0으로 채움.
2. 효율성:
   • 시간 복잡도 O(n), 공간 복잡도 O(1).
3. 장점:
   • 단순하면서도 효율적이며 문제의 제약 조건을 만족.

 

 

https://youtu.be/Tt3poT5qOqI?si=JaQhQAgcm2HvNy2b

 

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j = 0  # `j` 포인터: 배열을 순회하며 0이 아닌 숫자를 찾는 역할
        i = 0  # `i` 포인터: 0이 아닌 숫자를 저장할 위치

        # 첫 번째 루프: 0이 아닌 숫자를 앞으로 이동
        while j < len(nums):
            if nums[j] != 0:  # 0이 아닌 숫자인 경우
                nums[i] = nums[j]  # `i` 위치에 숫자를 저장
                i += 1  # 다음 저장 위치로 이동
            j += 1  # 다음 숫자를 확인

            # 현재 상태를 주석으로 표시:
            # 예제 1: nums = [0, 1, 0, 3, 12]
            # j = 0 -> nums[0] == 0 -> 아무 작업 안 함, i = 0
            # j = 1 -> nums[1] == 1 -> nums[0] = 1, i = 1
            # j = 2 -> nums[2] == 0 -> 아무 작업 안 함, i = 1
            # j = 3 -> nums[3] == 3 -> nums[1] = 3, i = 2
            # j = 4 -> nums[4] == 12 -> nums[2] = 12, i = 3
            # 중간 결과: nums = [1, 3, 12, 3, 12], i = 3, j = 5

        # 두 번째 루프: 배열의 남은 부분을 모두 0으로 채움
        while i < len(nums):
            nums[i] = 0  # 나머지 공간을 0으로 설정
            i += 1

            # 현재 상태를 주석으로 표시:
            # 예제 1: nums = [1, 3, 12, 3, 12], i = 3
            # i = 3 -> nums[3] = 0 -> nums = [1, 3, 12, 0, 12]
            # i = 4 -> nums[4] = 0 -> nums = [1, 3, 12, 0, 0]
            # 최종 결과: nums = [1, 3, 12, 0, 0]

 

https://youtu.be/aayNRwUN3Do?si=PME91ZD3KUiTZO3k

 

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left_idx = 0

        for right_idx in range(len(nums)):
            if nums[right_idx] != 0:
                nums[left_idx], nums[right_idx] = nums[right_idx], nums[left_idx]
                left_idx += 1