[leetcode] 75. Sort Colors

문제 설명

링크
정렬

접근 - Count

• 0, 1, 2, 의 개수 세기
• 대입

코드

    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero = one = two = 0
        for idx in range(len(nums)):
            if nums[idx] == 0:
                zero += 1
            elif nums[idx] == 1:
                one += 1
            else:
                two += 1
        for idx in range(len(nums)):
            if zero > 0:
                nums[idx] = 0
                zero -= 1
            elif one > 0:
                nums[idx] = 1
                one -= 1
            else:
                nums[idx] = 2

접근 2 - Swap

• l, r two pointers
• l 은 0의 위치 r 은 2의 위치
• 1 보다 느림

코드 2

    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        idx = l = 0; r = len(nums) - 1
        while idx <= r:
            if nums[idx] == 0:
                nums[idx], nums[l] = nums[l], nums[idx]
                l += 1
                idx += 1
            elif nums[idx] == 2:
                nums[idx], nums[r] = nums[r], nums[idx]
                r -= 1
            else: idx += 1