LeetCode 75. Sort Colors

파이썬 알고리즘 인터뷰 63번(리트코드 75) Sort Colors
https://leetcode.com/problems/sort-colors/

나의 풀이1

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

• 이게 출제 의도는 아니겠지..?

나의 풀이2

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

        while i < len(nums):
            if i < len (nums) - 1 and nums[i] > nums[i + 1]:
                nums[i] , nums[i + 1] = nums[i + 1], nums[i]
            elif i > 0 and nums[i - 1] > nums[i]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
                i -= 1
            else:
                i += 1

            

• 느리다.

나의 풀이3

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        cnt_0, cnt_1, cnt_2 = 0, 0, 0
        for num in nums:
            if num == 0:
                cnt_0 += 1
            elif num == 1:
                cnt_1 += 1
            else:
                cnt_2 += 1
        nums[:] = [0] * cnt_0 + [1] * cnt_1 + [2] * cnt_2

다른 풀이

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left, mid, right = 0, 0, len(nums) - 1
        
        while mid <= right:
            if nums[mid] == 0:
                nums[left], nums[mid] = nums[mid], nums[left]
                left += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1