[코테] 리트코드 정렬 75. Sort Colors

75. Sort Colors

문제 링크

https://leetcode.com/problems/sort-colors/description/

문제 설명

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

제한 사항

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

입출력 예 #1

1. Input : nums = [2,0,2,1,1,0]
2. Output : [0,0,1,1,2,2]

입출력 예 #2

1. Input : nums = [2,0,1]
2. Output : [0,1,2]

문제 풀이

red와 white는 0, blue는 배열의 맨 끝에서 시작하여 white와 blue가 동일한 위치에 있을 때 까지 반복한다.

반복하면서 배열의 값이 0이면 왼쪽으로 2이면 오른쪽으로 swap하여 정렬을 진행한다.

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

        while white < blue :
            if nums[white] < 1:
                nums[red], nums[white] = nums[white], nums[red]
                white += 1
                red += 1
            elif nums[white] > 1:
                blue -= 1
                nums[white], nums[blue] = nums[blue], nums[white]
            else :
                white += 1