283. Move Zeroes

Move Zeroes - LeetCode

1. 우선순위 큐를 이용해 zero index를 관리하는 해결법

from typing import *
from heapq import *


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        q = []
        for i in range(len(nums)):
            if nums[i] == 0:
                q.append(i)
        heapify(q)
        for i in range(len(nums)):
            if nums[i] == 0:
                continue
            else:
                if q:
                    zero_index = q[0]
                    if i < zero_index:
                        continue
                    zero_index = heappop(q)
                    nums[zero_index], nums[i] = nums[i], nums[zero_index]
                    heappush(q, i)

주어진 nums를 늘리거나 새 nums를 만들면 안 된다는 조건이었기 때문에 통과했다.

 

2. (정해) last zero index를 선형 탐색으로 관리 

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

예제를 시뮬레이션하면 아래와 같다.

index = 0, last_zero_index = 0
[0, 1, 0, 3, 12]
index = 1, last_zero_index = 0+1=1
[1, 1, 0, 3, 12]
index = 2, last_zero_index = 1
[1, 1, 0, 3, 12]
index = 3, last_zero_index = 1+1=2
[1, 3, 0, 3, 12]
index = 4, last_zero_index = 2+1=3
[1, 3, 12, 3, 12]

last_zero_index ~ len(nums) -> 0 으로 만들기
[1, 3, 12, 0, 0]

 

 

개인적으로 사연이 있는 문제였고, 좋은 정보도 얻게 되었다. 다시는 잊지 말아야겠다.