LeetCode 283(Move Zeroes, Python)

1. 문제 링크

• https://leetcode.com/problems/move-zeroes/description/

Move Zeroes - LeetCode

 

2. 문제 설명

• 정수로 구성된 array nums가 있을 때, 값이 0인 elements를 뒤로 옮기기. (그 외의 elements들은 상대적 순서를 유지해야 한다.)
• 여기서 조건은 in-place로, array를 copy하지 않고 이동시켜야 하는 것
• 예시1) nums = [0,1,0,3,12]이면, output = [1,3,12,0,0]이 되고
• 예시2) nums = [0]이면, output = [0]이 된다.

 

3. 처음 풀이 

• 처음에 그냥 정말 naive하게 생각해서, 0이 나오면 remove하고, 뒤에 append하는 걸 반복해봤다. (역시나 runtime이 구렸다.)
• inplace이기 때문에, index를 기준으로 pop을 하려면 추가 작업이 필요하니, 아래처럼 작성했는데 역시나 runtime 하위 10%가 나왔다.

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

• 만약, 그럼에도 이런 방식으로 풀고싶다면 아래처럼 index를 기준으로 pop을 하지만,
  • nums[i]==0인 경우(pop을 한 경우에는) index (여기서는 i)를 더하지 않고, 
  • 그 외의 경우에만 i+=1를 하였다.
  • 마지막에 0이 등장한 count를 세서 그만큼 nums 뒤에 붙여주는 식.
• runtime은 60%정도로, 다른 방식으로 하면 더 개선이 가능해보였다. 

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

        while i < len(nums) -1 :
            if nums[i] == 0 :
                cnt += 1
                nums.pop(i)
            else:
                i += 1
            
        nums += [0] * cnt

4. 다른 풀이

• two pointer를 활용한 풀이
• 훨씬 깔끔한 코드이다.
• 우선 slow = 0으로 초기값을 셋팅하고, 
  • for문을 돌리면서, fast라는 변수를 한칸씩 이동시킨다.
  • 여기서, 만약 nums[slow]가 0인데, nums[fast]가 0이 아니라면, 두개의 순서를 바꿔주고, 
  • slow가 0이 아니라면, slow를 오른쪽으로 한칸씩 이동시킨다. 
• 예를들어, [0,1,0,3,12]가 iteration을 돌게 되면
  • 처음에는 slow, fast = 0,0 이어서 조건에 해당되는게 없으니 pass하고
  • slow, fast = 0,1,이고, nums[fast]가 0이 아니기 때문에, [1,0,0,3,12]가 된다. 
  • slow, fast = 0,2가 되는데, nums[slow]=1로 0이 아니기 때문에, slow +=1이 되고,
  • slow, fast = 1,3에서, nums[slow]=0이고, nums[fast]!=0이므로, 순서를 바꿔서, [1,3,0,0,12]가 된다.
  • 이를 반복하다보면 [1,3,12,0,0]이 된다.

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

        for fast in range(len(nums)):
            if (nums[slow] == 0 and nums[fast] != 0) :
                nums[slow] , nums[fast] = nums[fast], nums[slow]
            if nums[slow] != 0:
                slow += 1