0, 1, 2로만 이루어진 배열이 주어졌을 때, 모든 0은 1보다 앞에, 모든 2는 맨 뒤에 오도록 배열 전체를 제자리(in-place)에서 정렬해야 합니다. 별도의 배열을 만들지 않고 단 한 번의 순회로 문제를 해결할 수 있는 대표적인 방법이 바로 DNF(네덜란드 국기, Dutch National Flag) 정렬 알고리즘입니다.
입력 예시 1 −
arr[ ] = {2, 0, 0, 1, 2, 1}출력 −
0 0 1 1 2 2
설명 − DNF 정렬 알고리즘으로 0, 1, 2를 포함한 배열을 정렬하면 {0, 0, 1, 1, 2, 2}가 출력됩니다.
입력 예시 2 −
arr[ ] = {0, 1, 1, 2, 1, 1, 0}출력 −
0 0 1 1 1 1 2
설명 − 같은 방식으로 정렬하면 {0, 0, 1, 1, 1, 1, 2}가 출력됩니다.
문제 해결 접근 방법
0, 1, 2로만 구성된 배열은 세 개의 포인터를 활용하는 DNF 정렬 알고리즘으로 매우 효율적으로 정렬할 수 있습니다.
DNF 정렬 알고리즘이란? − 이 알고리즘은 3개의 포인터(low, mid, high)를 사용해 배열을 순회하면서 필요한 원소들을 서로 교환(swap)하는 방식으로 동작합니다. 이름은 네덜란드 국기의 빨강·흰색·파랑 세 가지 색에서 유래했으며, '네덜란드 국기 문제'라는 이름으로도 널리 알려져 있습니다.
배열의 시작 지점에
low포인터를, 끝 지점에high포인터를 둡니다.배열의 처음부터 끝까지 순회하는
mid포인터를 생성합니다.mid가 가리키는 값이 '0'이면low위치의 원소와 교환한 뒤,low와mid를 각각 1씩 증가시킵니다.mid가 가리키는 값이 '2'이면high위치의 원소와 교환한 뒤,high만 1 감소시킵니다(mid는 그대로 유지).mid가 가리키는 값이 '1'이면 교환 없이mid만 1 증가시킵니다.
자바 예제 코드
public class Solution {
// DNF(네덜란드 국기) 정렬: 0, 1, 2를 제자리에서 정렬
public static void dnfSort(int arr[], int n) {
int low = 0;
int mid = 0;
int high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) {
// 값이 0이면 low와 교환 후 두 포인터 모두 앞으로 이동
int temp = arr[mid];
arr[mid] = arr[low];
arr[low] = temp;
low++;
mid++;
} else if (arr[mid] == 1) {
// 값이 1이면 교환 없이 다음 원소로 이동
mid++;
} else {
// 값이 2이면 high와 교환 후 high만 뒤로 이동
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
high--;
}
}
}
public static void print(int arr[], int n) {
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args) {
int arr[] = {0, 0, 1, 0, 1, 0, 1, 2, 2};
int n = arr.length;
dnfSort(arr, n);
print(arr, n);
}
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
0 0 0 0 1 1 1 2 2
시간 및 공간 복잡도
- 시간 복잡도: O(n) −
mid포인터가 배열을 단 한 번만 순회하므로 선형 시간 안에 정렬이 완료됩니다. - 공간 복잡도: O(1) − 추가 메모리 없이 입력 배열 내에서 원소 교환만으로 정렬이 이루어집니다.
마무리
DNF 정렬은 0, 1, 2처럼 값의 종류가 세 가지뿐인 배열을 정렬할 때 가장 효율적인 방법 중 하나입니다. 일반적인 비교 기반 정렬(O(n log n))보다 빠르고, 제자리 정렬이 가능해 메모리 효율성도 뛰어납니다. 코딩 테스트에서 '네덜란드 국기 문제'로 자주 출제되는 만큼, 세 포인터의 이동 규칙과 교환 조건을 확실히 익혀두시길 권장합니다.