[LEETCODE] 75: Sort Colors(Python)

Sort Colors - LeetCode

문제 설명

0,1,2 세 종류의 색이 등장할 때 인플레이스로 정렬해보자. 정렬 함수를 사용하지 않고 풀어야 한다.

나의 풀이

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        d={0:0,1:0,2:0}
        for i in nums:
            d[i]+=1
        
        start=0
        end=0
        for i in range(3):
            end+=d[i]
            for j in range(start,end):
                nums[j]=i
            start+=d[i]

색이 0,1,2 세 가지이므로 각 색의 등장 빈도를 센다. 이후 0,1,2 순서대로 등장한 개수만큼 nums 원소를 업데이트해주면 된다.

시간복잡도

딕셔너리 작성에 O(n), nums 업데이트에 O(n)이 걸린다.