문제 소개
0, 1, 2로만 구성된 배열이 주어졌을 때, 모든 0은 1보다 앞쪽에, 모든 2는 맨 뒤쪽에 오도록 요소를 정렬해야 합니다. 이때 추가 메모리 없이 배열 자체에서 정렬을 수행하는 제자리(in-place) 정렬이어야 한다는 점이 핵심입니다.
이 문제는 DNF(Dutch National Flag, 네덜란드 국기) 정렬 알고리즘을 사용하면 시간 복잡도 O(n), 공간 복잡도 O(1)로 효율적으로 해결할 수 있습니다.
입력 예제 1
입력 −
arr[ ]= {2,0,0,1,2,1 }
출력 −
0 0 1 1 2 2
설명 − 0, 1, 2를 포함한 배열을 DNF 정렬 알고리즘으로 정렬하면 {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개의 포인터를 사용해 배열 전체를 순회하면서 필요한 요소들을 서로 교환(swap)합니다.
- 배열의 시작 위치에 low 포인터를, 끝 위치에 high 포인터를 둡니다.
- 배열의 중간 지점을 기준으로 mid 포인터를 만들어, 배열의 처음부터 끝까지 순회합니다.
- mid가 가리키는 값이 '0'이면 low가 가리키는 요소와 교환한 뒤, low와 mid를 각각 하나씩 증가시킵니다.
- mid가 가리키는 값이 '2'이면 high가 가리키는 요소와 교환한 뒤, high를 하나 감소시킵니다. (교환으로 들어온 값은 아직 검사되지 않았으므로 mid는 그대로 둡니다.)
- mid가 가리키는 값이 '1'이면 mid만 증가시킵니다.
이 과정을 mid가 high를 넘지 않을 때까지 반복하면 0은 앞쪽에, 1은 중간에, 2는 뒤쪽에 자연스럽게 모이게 됩니다.
구현 예제
#include<iostream>
using namespace std;
void dnfsort(int a[], int n){
int low= 0;
int high= n-1;
int mid=0;
while(mid<=high){
if(a[mid]==0){
swap(a[mid],a[low]);
mid++;
low++;
}
if(a[mid]==1){
mid++;
}
if(a[mid]==2){
swap(a[mid],a[high]);
high--;
}
}
}
int main(){
int a[]= {1,0,0,2,1,1,0,0,1};
int n= sizeof(a)/sizeof(int);
dnfsort(a,n);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
}
참고로, 한 번의 순회에서 여러 조건이 연달아 실행되는 것을 방지하려면 각 분기를 else if로 연결하는 것이 더 안전합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
0 0 0 0 1 1 1 1 2