[파이썬 알고리즘] 17장 - 색 정렬 (leetcode 75) - 3 pointer 문제

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

Sort Colors - LeetCode

<문제>

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.

 

<예시>

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

 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 0 - red, 1 - white, 2 - blue
        mid_value = 1
        left, cur, right = 0, 0, len(nums)
        while cur < right:
            if nums[cur] < mid_value:
                nums[left], nums[cur] = nums[cur], nums[left]
                left += 1   # 가장 최근에 위치한 0 다음 위치를 가리키고 있다
                cur += 1    # 계속 이동하는 포인터
            elif nums[cur] == mid_value:
                cur += 1
            else:
                right -= 1
                nums[right], nums[cur] = nums[cur], nums[right]

---

en.wikipedia.org/wiki/Dutch_national_flag_problem#:~:text=The%20algorithm%20indexes%20three%20locations,middle%20and%20the%20top%20group.

Dutch national flag problem - Wikipedia

 

• left : 가장 오른쪽에 위치한 0 바로 다음 위치를 가리키는 포인터 (=다음에 0이 들어갈 자리를 가리키는 포인터)
• cur : 이동하는 포인터
• right : 가장 왼쪽에 위치한 2의 위치를 가리키는 포인터 (=right-1은 다음에 2가 들어갈 자리를 가리키는 포인터)

 

* 위의 문제에서는 mid가 1인 경우

• list[cur] < mid
  • list[left]와 list[cur]을 교환하고, left, cur 모두 1씩 증가
  • 즉, mid보다 작은 수를 왼쪽으로 옮기고 현재 위치 1증가
  • (left도 1증가해주는 이유는 현재 0이 옮겨진 다음 위치에 또 다른 0이 들어오기를 기다려야 하기 때문)

• list[cur] == mid
  • 그냥 현재 위치를 1증가 (별다르게 해줄 일 없다. 정렬조건 만족하니까!)
• list[cur] > mid
  • right -- 해준 뒤, list[right]와 list[cur] 교환해준다.
  • 이 때 cur을 따로 조정해주지 않는 이유는 mid보다 큰 수를 오른쪽으로 옮긴것은 확실하지만,
    cur자리에 옮겨진 값이 mid보다 작은지, 큰지, 같은지 전혀 모르기 때문에 cur를 옮기지 않는 것이다.