Python으로 색상 정렬 문제 해결하기: 네덜란드 국기 알고리즘 완벽 가이드

문제 개요

n개의 객체로 이루어진 배열이 있고, 각 객체는 빨강(0), 흰색(1), 파랑(2) 중 하나의 색으로 표현된다고 가정해 보겠습니다. 이때 같은 색상의 객체들이 서로 인접하도록 배열을 제자리(in-place)에서 정렬해야 하며, 색상의 순서는 반드시 빨강 → 흰색 → 파랑 순이어야 합니다.

예를 들어 입력 배열이 [2,0,2,1,1,0]이라면, 정렬 결과는 [0,0,1,1,2,2]가 됩니다.

접근 방법: 네덜란드 국기 알고리즘

이 문제는 세 개의 포인터(low, mid, high)를 활용하는 네덜란드 국기(Dutch National Flag) 알고리즘으로 단 한 번의 순회만에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• low : 0(빨강) 영역의 다음 경계를 가리킴
• mid : 현재 검사 중인 원소를 가리킴
• high : 2(파랑) 영역의 이전 경계를 가리킴

알고리즘 단계

1. low = 0, mid = 0, high = 배열 길이 - 1로 초기화합니다.
2. mid <= high인 동안 다음을 반복합니다.
   • arr[mid] == 0이면 arr[mid]와 arr[low]를 교환한 뒤, low와 mid를 각각 1씩 증가시킵니다.
   • arr[mid] == 2이면 arr[mid]와 arr[high]를 교환한 뒤, high만 1 감소시킵니다. (교환 후 들어온 값은 아직 검사하지 않았으므로 mid는 그대로 둡니다.)
   • 그 외(arr[mid] == 1)에는 mid만 1 증가시킵니다.

Python 구현 예제

아래 코드를 통해 동작 방식을 더 쉽게 이해할 수 있습니다.

class Solution(object):
    def sortColors(self, nums):
        low = 0
        mid = 0
        high = len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 2:
                nums[high], nums[mid] = nums[mid], nums[high]
                high -= 1
            else:
                mid += 1
        return nums

ob1 = Solution()
print(ob1.sortColors([2, 0, 2, 1, 1, 0]))

입력

[2,0,2,1,1,0]

출력

[0,0,1,1,2,2]

복잡도 분석

• 시간 복잡도: O(n) — 배열의 각 원소를 최대 한 번씩만 검사하므로 선형 시간에 처리됩니다.
• 공간 복잡도: O(1) — 추가 메모리 없이 입력 배열 내부에서 교환만 수행하는 제자리 정렬입니다.

이처럼 네덜란드 국기 알고리즘은 정렬 대상 값의 종류가 3개로 제한된 경우 매우 효율적인 선택지가 되며, 퀵소트의 3-way 파티셔닝에도 응용될 수 있는 강력한 기법입니다.