[Algorithm][LeetCode 75][Medium] Sort Colors

문제

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.

Example 1

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Follow up

Could you come up with a one-pass algorithm using only constant extra space?

---

솔루션

1. 주요 제약 조건

1. sort 메서드 없이 풀 것
2. 배열을 한 번만 순회할 것 (one-pass)
3. 추가 공간 없이 풀 것 (constant extra space)
4. 원본 배열을 직접 바꿀 것 (in-place)

2. 처음 시도한 풀이 (제약 조건 미충족)

var sortColors = function(nums) {
    let num1Count = 0;
    let num2Count = 0;
    let num0Count = 0;
    while(nums.length) {
        const num = nums[0];
        if (num == 1) {
            nums.splice(0, 1);
            num1Count++;
        } else if (num == 2) {
            nums.splice(0, 1);
            num2Count++;
        } else if (num == 0) {
            nums.splice(0, 1);
            num0Count++;
        }
    }

    nums.unshift(...Array(num0Count).fill(0));
    nums.push(...Array(num1Count).fill(1));
    nums.push(...Array(num2Count).fill(2));
};

이 코드의 문제점

항목	왜 문제인가?	위배되는 조건
Array(n).fill()	새로운 배열을 생성하여 추가 공간 사용	constant space 위반
splice + push/unshift	배열을 반복적으로 재구성하며 메모리 복사/이동 발생	in-place의 실질적 의미 위반
3-pass 방식	1) 전체 순회 2) 0 추가 3) 1, 2 추가	one-pass 위반
splice 사용	splice(0, 1)는 O(n)이므로 루프 안에서 쓰면 전체 O(n²)	성능 저하

3. 최종 솔루션 (Dutch National Flag Algorithm)

핵심 아이디어

1. 포인터 세 개를 사용한다: low, mid, high
2. mid를 순회 포인터로 두고, nums[mid] 값에 따라 다음 세 가지 행동을 한다:
   • 0일 경우: nums[low]와 swap하고 low++, mid++
   • 1일 경우: 그대로 mid++
   • 2일 경우: nums[high]와 swap하고 high--만 수행 (mid는 그대로)
3. mid > high가 되면 종료

코드

var sortColors = function(nums) {
    let low = 0, mid = 0, high = nums.length - 1;
    while(mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else if (nums[mid] === 2) {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
        }
    }
};

주의할 점

• 2를 만났을 때 mid를 증가시키지 않는 이유는, nums[high]에서 가져온 값이 무엇인지 모르기 때문입니다. 따라서 mid 위치에서 다시 검사해야 합니다.
• 0을 만났을 때는 항상 mid를 증가시켜도 괜찮습니다. low 포인터는 항상 mid보다 앞에 있기 때문에 이미 처리된 값만 가지고 있습니다.