정렬 문제는 알고리즘 문제에서 아주 고전적인 문제입니다. 하지만 이번에 소개할 것은, 색다른 형태의 정렬 문제로, 내용은 다음과 같습니다.

“0, 1, 2만으로 이루어진 배열을 1번의 순회만 써서 정렬할 수 있을까?”

예를 들면, [0, 1, 2, 2, 1, 0, 2, 1 ]로 이루어진 배열을 정렬한다면, [0, 0, 1, 1, 1, 2, 2, 2]가 나와야 합니다. 당연히 이 문제는 O(n) 만에 풀이가 가능합니다. 배열을 쭉 순회하면서 0의 개수, 1의 개수, 2의 개수를 센 다음에 0를 0의 개수만큼 출력하고, 1을 1의 개수만큼 출력하고, 2를 2의 개수만큼 출력하면 문제의 답을 얻을 수 있기 때문입니다.

하지만, 문제의 조건은 ‘1번의 순회’입니다. {0,1,2}의 개수를 세는 데에 순회를 한 번 하고, 정답을 재구성하는 데에 순회를 한 번 더 하게 됩니다. 그래서 개수를 세고 재구성하는 방식으로는 문제를 해결할 수 없습니다.

단순하게 생각해보기

0, 1로 이루어진 배열에 대해서는 조금 쉽게 접근이 가능합니다. 예를 들어, 다음과 같은 배열을 정렬하는 문제를 푸는 상황에 놓여있다고 해봅시다.

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

이런 경우, 양쪽에서 범위를 좁혀가면서 0과 1을 교체하면 정렬이 가능합니다. 앞에서부터 순회하면서 1을 만날 때마다 뒤쪽에 있는 원소와 교환하는 전략을 취하면 됩니다. ^와 @를 배열을 추적하는 두 개의 포인터로 표시하였습니다.

[0, 1, 0 ,1, 1, 0, 1, 0]
 ^                    @
    ^                 @  (Met 1. Exchange)
[0, 0, 0, 1, 1, 0, 1, 1]
       ^           @
          ^        @     (Met 1. Exchange)
          ^     @        (Met 1. Exchange)
[0, 0, 0, 0, 1, 1, 1, 1]
             ^@          (Terminate)

0, 1, 2로 이루어진 경우

0, 1로 이루어진 배열과 비슷하지만 조금 더 어렵습니다. 0과 1을 다르게 처리하기 위해 하나의 포인터를 추가하여 알고리즘을 설계해야 합니다.

void sortColors(vector<int>& nums) {
    int i=0;
    int j=0;
    int k = nums.size()-1;

    while (j <= k){
        switch (nums[j]){
            case 0:
                std::swap(nums[i++], nums[j++]);
                break;
            case 1:
                j++;
                break;
            case 2:
                std::swap(nums[j], nums[k--]);
                break;
        }
    }
    return;
}

예를 들어서 보면 다음과 같이 작동합니다. $, ^, @ 세 개의 포인터가 각각 i, j, k를 나타냅니다.

[2, 1, 0, 2, 1, 2, 0, 1]
 $^                   @
[1, 1, 0, 2, 1, 2, 0, 2]
 $^                @
 $  ^              @
 $     ^           @
[0, 1, 1, 2, 1, 2, 0, 2]
    $     ^        @
[0, 1, 1, 0, 1, 2, 2, 2]
    $     ^     @
[0, 0, 1, 1, 1, 2, 2, 2]
       $     ^  @
          $    ^@

이 알고리즘은 0번째부터 $까지는 0을 넘겨버리고, @부터 마지막까지는 2를 넘겨버리는 방식으로 작동합니다. 예시처럼 손으로 돌려보면 멋지게 작동하는 것을 볼 수 있지만, 이렇게 간단한 구조로 설계하기는 쉽지 않다는걸 해보면 알 수 있을 것입니다. (LeetCode에서도 풀어볼 수 있습니다¹) 이 문제는 그래프 알고리즘으로 유명한 Dijkstra가² 생각해냈다고 합니다.