leetcode medium : sort colors (sort 구현 문제)

Sort Colors - LeetCode

Sort Colors - LeetCode

 

sort를 직접 구현하는 문제다.

나는 quicksort를 구현했다.

내가 구현한 방법이 굉장히 구현난이도가 낮은 방법이다.

옛날에 이걸로 많이 구현했었는데 한동안 안써서 기억이 안났다.

오늘 기억난 김에 확실하게 다시 복습해야겠다.

 

class Solution:
    
    def qsort(self, nums, low, high):
        if low >= high:
            return
        

        #while문 쓰고 난리치는 것보다 이게 훨씬 구현하기 쉽다
        p = low + 1
        for i in range(low + 1, high + 1):
            if nums[i] <= nums[low]:
                nums[p], nums[i] = nums[i], nums[p]
                p += 1
                
        p -= 1
        nums[low], nums[p] = nums[p], nums[low]
        self.qsort(nums, low, p - 1)
        self.qsort(nums, p + 1, high)
    
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        self.qsort(nums, 0, len(nums) - 1)