Sort Colors

라이브러리 정렬은 O(n log n)에 끝나지만, 문제에서는 이를 금지합니다. 면접관은 값이 세 종류뿐이라는 사실을 어떻게 활용하는지 보고 싶어 하기 때문입니다. 따라서 기본 방법은 직접 작성하는 정렬이며, 올바르게 구현하기 가장 간단한 방법은 버블 정렬입니다. 배열을 훑으면서 이웃한 두 값의 순서가 잘못되어 있으면 서로 바꿉니다.

한 번 훑을 때마다 마주치는 값 중 가장 큰 값이 거품처럼 위로 떠오르듯 배열의 맨 끝까지 이동합니다. 첫 번째 순회가 끝나면 마지막 위치가 확정되고, 두 번째 순회가 끝나면 마지막 두 위치가 확정됩니다. 따라서 n-1번 순회하면 배열 전체가 정렬됩니다. [2, 1, 0]에서는 첫 번째 순회로 2가 맨 끝으로 이동해 [1, 0, 2]가 되고, 두 번째 순회에서 1과 0의 위치를 바꿉니다.

각 순회에서 아직 위치가 확정되지 않은 모든 쌍을 비교하므로 느립니다. 비교 횟수는 전체적으로 약 n²/2회입니다. n = 1.5 × 10^4이면 비교 횟수가 10^8회를 넘고, 처음부터 순서가 잘못된 모든 쌍을 바꾸는 작업도 추가됩니다. 게다가 이 작업 중 어느 것도 값이 세 종류뿐이라는 사실을 활용하지 않습니다.

버블 정렬은 이웃한 값들을 비교하는 데 모든 시간을 쓰지만, 어떤 값들이 있는지는 이미 알고 있습니다. 배열에 0이 두 개, 1이 세 개, 2가 두 개 있다면, 아무것도 옮기기 전에 답은 정해져 있습니다. 0 두 개, 1 세 개, 2 두 개입니다. 개수만 중요합니다.

그러니 배열을 한 번 읽으며 각 값의 개수를 세세요. 그런 다음 처음부터 배열을 덮어쓰세요. count[0]개만큼 0을 쓰고, 이어서 count[1]개만큼 1을 쓰고, 그다음 count[2]개만큼 2를 씁니다. 이것이 계수 정렬이며, 같은 값끼리는 서로 바꾸어도 되므로 여기서는 안전합니다. 1은 그저 1이므로 원래 순서를 유지할 필요가 없습니다.

이 방법은 두 번 순회하고 카운터 세 개를 사용하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 제약 조건을 충족하며, 색상이 여러 개일 때 자연스러운 해법입니다. 이 문제가 유명한 후속 질문은 배열을 한 번만 읽으면서도 이 작업을 할 수 있느냐는 것입니다.

읽으면서 세 구간을 만드세요. 앞쪽에는 0, 그 뒤에는 1, 뒤쪽에는 2를 두고, 1과 2 사이에는 아직 읽지 않은 부분을 둡니다. 세 개의 인덱스가 경계를 표시합니다. low 앞의 모든 값은 0이고, low부터 mid 미만까지는 모두 1이며, high 뒤의 모든 값은 2입니다. nums[mid]부터 nums[high]까지는 아직 읽지 않은 상태입니다.

nums[mid]를 읽습니다. 1은 이미 해당 구간에 있으므로 mid를 앞으로 이동합니다. 0은 앞쪽에 있어야 합니다. nums[low]와 교환하고 low와 mid를 모두 앞으로 이동합니다. low에서 돌아온 값은 1(또는 아직 1을 본 적이 없다면 같은 0)이므로 이미 제자리에 있습니다. 2는 뒤쪽에 있어야 합니다. nums[high]와 교환하고 high를 뒤로 이동하되, mid는 그대로 둡니다. high에서 온 값은 아직 읽지 않았기 때문입니다.

각 단계에서 mid는 앞으로 이동하거나 high는 뒤로 이동하므로, 읽지 않은 부분은 매번 한 칸씩 줄어들고 반복문은 n단계 뒤에 끝납니다. [2, 0, 2]를 추적해 봅시다. 첫 번째 2를 마지막 2와 교환하고 high를 1로 줄입니다. 인덱스 0에는 여전히 2가 있으므로 0과 교환하고 high를 0으로 줄입니다. 이제 인덱스 0에는 0이 있으므로 그대로 두면 [0, 2, 2]가 됩니다.