75. Sort Colors

Solution 1 - 단순 배열 구현

1. 각 색상의 개수를 저장하는 배열을 만든다.
2. 만든 배열을 사용해서 nums의 내용을 바꾼다.

이 방법은 색상의 종류가 0, 1, 2로 한정되어있기 때문에 통하는 방법 아닐까? 이게 좋은 코드인가?

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        list = [0 for i in range(3)]
        for i in range(len(nums)): # O(n)
            list[nums[i]] += 1
        idx = 0
        for i in range(3):
            for j in range(list[i]):
                nums[idx] = i
                idx += 1

시간 복잡도

nums의 길이 만큼 돌면서 색상의 각 개수를 저장하고, 그 저장값을 사용해 nums의 내용을 모두 변경하므로 O(2n), O(n)이다.

Solution 2 - 쓰리 포인터

더 빠른 속도의 코드를 보던 중에 쓰리 포인터를 이용하는 방법을 찾았다. 처음에는 이분 탐색인 줄 알았는데, 정렬된 배열이 아니므로 이분 탐색이 아니다.

세 개의 포인터를 이용하여 0은 가장 왼쪽으로, 2는 가장 오른쪽으로 보내는 방법이다.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low = 0 
        mid = 0
        high = len(nums) - 1

        while mid <= high:
            if nums[mid] == 0: # 0 이면 가장 앞의 숫자와 교체
                temp = nums[mid]
                nums[mid] = nums[low]
                nums[low] = temp
                low += 1
                mid += 1
            elif nums[mid] == 1: # 1 이면 그냥 다음으로 이동
                mid+=1
            else: # 2 이면 가장 뒤의 숫자와 교체
                temp = nums[mid]
                nums[mid] = nums[high]
                nums[high] = temp
                high -= 1
        return nums

시간 복잡도

이분 탐색인 줄 알고 더 빠른 방법을 찾았다고 좋아했었는데.. 결국 이것도 O(n) 이다.