[Leetcode]283. Move Zeroes(n^2말고 다른풀이로 풀어볼것)

1. problem :

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

 

2. solution 1 :

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        zero_count = nums.count(0) 
        i = 0
        while zero_count > 0:
            if nums[i] == 0:
                nums.pop(i)
                nums.append(0) 
                zero_count -= 1
            else:
                i += 1 
        return nums

O(n^2) 풀이다. 하하. 나는 이 정도밖에 생각을 못했다. i값이 ==0이라면, 빼고, append(0)을 한다. i값이 0이 아니라면, i+=1을 한다. 일차원적인 사고다. 

 

3. solution 2 :

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

last_non_zero_found_at이라는 변수를 설정해서, 0이면 가만히 두고, 0이 아니라면 그 값에 nums [i]를 넣고, last를 갱신한다. 이 방법이 뭔가 이해되는 것 같으면서도 완벽히 이해되지 않는다. 무의식에 계속 사고하도록 놔둬야겠다.

 

4. solution 3 : 

from typing import List 
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        snowball_size = 0 
        for i in range(len(nums)):
            if nums[i] == 0:
                snowball_size += 1 
            elif snowball_size > 0:
                temp = nums[i]
                nums[i] = 0 
                nums[i - snowball_size] = temp 
        return nums

와우 다른 분이 적은 solution이다. 0이 연속되어 있는 크기를 snowball_size라는 변수로 설정했다. 뭔가 확 와닿는다. 

nums [i]가 0이 아니라는 가정하에, snowball_size > 0 이면, temp에 nums [i]를 두고, nums [i] = 0으로 설정한 다음, nums [i-snowball_size] = temp로 설정한다. 참으로 멋있는 풀이다.