63. Sort Colors

리트코드

• 빨간색을 0, 흰색을 1, 파란색을 2라 할 때 순서대로 인접하는 제자리(In-Place) 정렬을 수행하라.

1. 네덜란드 국기 문제를 응용한 풀이

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
        

• 이 문제는 다익스트라가 1976년에 제안한 '네덜란드 국기 문제(Dutch National Flag Problem)' 문제와 동일한 문제로, 퀵 정렬의 개선 아이디어와도 관련이 깊다.

• 네덜란드 국기의 색깔인 붉은색(위), 흰색(중앙), 파란색(아래)을 세 부분으로 대입해 분할하는 것이다.

  • 피벗보다 작은 부분, 같은 부분, 큰 부분 이렇게 세 부분으로 분할(Three-Way Partitioning)하여 기존 퀵 정렬의 두 부분 분할에 비해 개선하는 방안을 제시하는 것이다.

• 이 문제는 매우 유명한 컴퓨터과학 분야 문제 중 하나이므로, 위키피디아에 이미 풀이 알고리즘이 제시되어 있다.

<네덜란드 국기 문제의 수도코드>

three-way-partition(A: array of values, mid: value):

    i <- 0
    j <- 0
    k <- size of A
    
    while j < k:
        if A[j] < mid:
            swap A[i] and A[j]
            i <- i + 1
            j <- j + 1
        
        else if A[j] > mid:
            k <- k - 1
            swap A[j] and A[k]
        else:
            j <- j + 1

• 이 수도코드는 i, k를 양쪽 포인터로 두고 j가 이동하면서 mid 값을 기준으로 스왑하는 형태로 구현되어 있다.

• 수도코드 알고리즘의 변수명을 각각의 국기 색깔에 대입해 i를 red로 k를 blue로, j는 white로 하고, 중앙 값을 지칭하는 mid는 원래의 값인 1로 변경해 본다.

• 예제의 입력값에서 보든 각각의 실제 값은 [0,1,2]로 정한다.

  • 이 정렬을 도식화하면 다음과 같다.

    

  • 이 그림에서 시작 시점에는 red, white모두 0에서 시작하고 blue는 배열의 길이가 된다.

  • 배열은 0부터 시작하므로 처음에 blue는 배열 인덱스의 바깥에 있다.

  • 비교가 시작되면서 1을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 스왑된다.

    • 이 때 red와 blue 는 각각 오른쪽과 왼쪽으로 이동하면서 간격이 점점 좁아지는 형태가 된다.

  • 투 포인터 풀이와 유사하며, 그 사이에 포인터가 하나 더 존재한다고 볼 수 있다.

  • white와 blue 사이는 계속 비교가 진행된다.

  • 마지막으로 비교가 완료될 때 red는 1보다 작은 인덱스인 +1 지점, blue는 1보다 큰 인덱스의 처음의 가리키게 되며

    white와 blue가 겹쳐지면서 비교가 완료된다.

• 수도코드와는 변수명이 다르고 mid 변수를 값 1로 직접 대입해서 풀이했다는 차이만 있을 뿐, 알고리즘은 완전히 동일하다.