[Leetcode/Two Pointer] 75. Sort Colors

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low, mid, high = 0, 0, len(nums) - 1  # 세 개의 포인터 설정

        while mid <= high:  # 중간 포인터(mid)가 high보다 작거나 같을 때까지 반복
            if nums[mid] == 0:  # 빨간색 (0)일 경우
                nums[low], nums[mid] = nums[mid], nums[low]  # low 위치와 mid 위치 값 교환
                low += 1  # low를 오른쪽으로 이동
                mid += 1  # mid도 이동
            elif nums[mid] == 1:  # 흰색 (1)일 경우
                mid += 1  # mid만 이동 (제자리에 둠)
            else:  # 파란색 (2)일 경우
                nums[mid], nums[high] = nums[high], nums[mid]  # mid와 high 위치 값 교환
                high -= 1  # high를 왼쪽으로 이동 (mid는 그대로)

코드 설명

low, mid, high 세 개의 포인터를 사용하여 배열을 정렬한다.

1. 초기 설정
   • low: 0을 배치할 위치
   • mid: 현재 검사 중인 위치
   • high: 2를 배치할 위치
2. while 반복문 (mid ≤ high)
   • nums[mid] == 0 (빨간색)
     • low와 mid를 swap하고 low와 mid를 증가
   • nums[mid] == 1 (흰색)
     • 그대로 두고 mid만 증가
   • nums[mid] == 2 (파란색)
     • mid와 high를 swap하고 high만 감소
       (주의: mid는 그대로 둠, 새롭게 스왑된 값이 0이나 1일 수 있기 때문)

 

시간 및 공간 복잡도

• 시간 복잡도: O(n), 리스트를 한 번만 순회
• 공간 복잡도: O(1), 추가적인 배열을 사용하지 않음

 

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