[리트코드] 75. Sort Colors - python

75. Sort Colors

문제

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.

sort() 라이브러리를 사용하지 않고 in-place로 배열 정렬하기

제한사항

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

풀이

0이 들어갈 위치를 가리키는 포인터

순회할 포인터

2가 들어갈 위치를 가리키는 포인터를 만든다.

[1, 0, 2, 2, 0, 1, 2, 1, 0]
^^                       ^
||                       |
idx0, i                 idx2

nums[i]가 0일 경우 idx0과 바꾸고 idx0과 i를 오른쪽으로 한칸 움직인다.

nums[i]가 2일 경우 idx2과 바꾸고 idx2를 한 칸 움직인다.

(움직인 idx2가 1일수도 있기 때문에 i는 움직이지 않는다.)

1일 경우 i를 한칸 움직인다.

i와 idx2가 교차될 경우 종료한다.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        idx0 = 0
        idx2 = len(nums) - 1
        i = 0
        while i <= idx2:
            if nums[i] == 0:
                nums[idx0], nums[i] = nums[i], nums[idx0]
                idx0 += 1
                i += 1
            
            elif nums[i] == 2:
                nums[idx2], nums[i] = nums[i], nums[idx2]
                idx2 -= 1
            
            else:
                i += 1
                continue