C#으로 추가 공간 없이 배열의 0과 1 정렬하는 방법 — 투 포인터 기법

개요

배열에 포함된 0과 1을 별도의 배열 같은 추가 메모리 공간 없이 정렬하려면 투 포인터(Two Pointers) 기법을 활용할 수 있습니다. 이 방법은 원본 배열 자체를 제자리(in-place)에서 수정하기 때문에 공간 복잡도가 O(1)로 매우 효율적입니다.

알고리즘 동작 방식

두 개의 포인터 low와 high를 선언합니다. low 포인터는 배열의 시작 위치를 가리키고, high 포인터는 주어진 배열의 끝 위치를 가리킵니다.

• arr[low]가 0이면 교환(swap)이 필요하지 않습니다.
• arr[low]가 1이면 교환이 필요합니다. 이때 high 위치의 값과 맞바꾼 후 high 포인터를 한 칸 감소시킵니다.
• low가 high보다 작은 동안 위 과정을 반복합니다.

시간 복잡도: O(N)

예제 코드

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

실행 결과

0 0 1 1 1 1

동작 원리 요약

위 예제에서 입력 배열 { 0, 1, 1, 0, 1, 1 }은 알고리즘 실행 후 모든 0이 앞쪽에, 모든 1이 뒤쪽에 배치됩니다. low 포인터는 왼쪽에서 오른쪽으로 이동하며 1을 발견하면, high 포인터가 가리키는 끝쪽 값과 교환합니다. 교환이 일어날 때마다 high는 감소하고, 0을 만나면 low만 증가하므로 두 포인터가 만나는 시점에는 배열 전체가 정렬되어 있습니다. 이처럼 투 포인터 기법은 단 한 번의 순회로 정렬을 완료하며, 임시 배열 없이 O(1)의 추가 공간만 사용한다는 점이 가장 큰 장점입니다.