[LeetCode] 283 - Move Zeroes

문제

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

정수 배열 nums가 주어지면, 0이 아닌 원소의 상대적인 순서를 유지하면서 모든 0을 끝으로 이동시키는 코드를 작성해라.

단, 배열 복사 없이 원본 배열을 교체해야 한다.

 

예시 )

# 예시 1
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

# 예시 2
Input: nums = [0]
Output: [0]

 

 

풀이 1

배열을 전체적으로 순환하면서 0인 수를 발견하면 한 칸씩 뒤로 미루는 방법이다.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        length = len(nums)
        # 배열 순회
        for i in range(length - 1):
            # 비교할 부분 순회
            for j in range(length - 1 - i):
                if nums[j] == 0:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]

단순하고 무식한 구현이지만, 반복문을 중첩하기 때문에 시간복잡도가 높은 풀이에 해당한다.

 

 

풀이 2

 

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        length = len(nums)
        for i in range(length - 1):
            if nums[i] == 0:
                idx = i
                for j in range(i, length):
                    if nums[j] != 0:
                        idx = j
                        break
                nums[i], nums[j] = nums[j], nums[i]

 

 

풀이 3

nums 배열에서 0이 아닌 원소를 순서대로 다른 배열에 저장해 두었다가, 원본 배열을 수정하는 방식이다. 

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        length = len(nums)
        # 0아 아닌 원소 저장
        none_zeros = [n for n in nums if n != 0]
        length_none_zeros = len(none_zeros)
        # 원본 배열 수정
        for i in range(length):
            nums[i] = none_zeros[i] if i < length_none_zeros else 0

원본 배열을 수정할 때는 원본 배열 길이만큼 반복하면서, 각 인덱스 마다 0이 아닌 원소를 복사해 놓은 배열에 값이 있는지 확인해야 한다.

 

 

참고 문서

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