C#으로 추가 공간 없이 0, 1, 2 정렬하기 – 네덜란드 국기(Dutch National Flag) 알고리즘

배열에 포함된 0, 1, 2를 추가 메모리 공간 없이 한 번의 순회로 정렬해야 하는 경우가 자주 있습니다. 이 문제는 유명한 네덜란드 국기(Dutch National Flag) 알고리즘을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 세 개의 포인터를 활용하여 배열을 세 개의 영역으로 나누는 것입니다.

알고리즘 동작 원리

low, mid, high라는 세 개의 포인터를 사용합니다. low와 mid는 배열의 시작 지점에서, high는 배열의 마지막 요소를 가리키도록 초기화합니다.

• arr[mid] == 0인 경우: arr[mid]와 arr[low]의 값을 서로 교환한 뒤, low와 mid 포인터를 각각 한 칸씩 앞으로 이동합니다.
• arr[mid] == 1인 경우: 교환이 필요하지 않습니다. mid 포인터만 한 칸 앞으로 이동합니다.
• arr[mid] == 2인 경우: arr[mid]와 arr[high]의 값을 서로 교환한 뒤, high 포인터만 한 칸 뒤로 이동합니다. 이때 mid는 그대로 유지합니다.

이 과정을 반복하면 0은 배열의 앞쪽에, 1은 중간에, 2는 뒤쪽에 자연스럽게 정렬됩니다.

시간 복잡도 − O(N) (배열을 한 번만 순회)
공간 복잡도 − O(1) (추가 공간 불필요)

C# 구현 예제

using System;
namespace ConsoleApplication{
    public class Arrays{
        private void Swap(int[] arr, int pos1, int pos2){
            int temp = arr[pos1];
            arr[pos1] = arr[pos2];
            arr[pos2] = temp;
        }
        public void DutchNationalFlag(int[] arr){
            int low = 0;
            int mid = 0;
            int high = arr.Length - 1;
            while (mid <= high){
                if (arr[mid] == 0){
                    Swap(arr, low, mid);
                    low++;
                    mid++;
                }
                else if (arr[mid] == 2){
                    Swap(arr, high, mid);
                    high--;
                }
                else{
                    mid++;
                }
            }
        }
}
class Program{
    static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr = { 2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 1 };
            a.DutchNationalFlag(arr);
            for (int i = 0; i < arr.Length; i++){
                Console.WriteLine(arr[i]);
            }
            Console.ReadLine();
        }
    }
}

실행 결과

0 0 0 0 1 1 1 1 2 2 2