LeetCode Sort Colors (JavaSciprt), three pointer

링크 : https://leetcode.com/problems/sort-colors/description/

문제 설명

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. 0, 1, 2를 정렬하기 위해 3개의 포인터 start, mid, end를 설정
2. start -> 0, mid -> 1, end -> 2를 나타냄
3. 정렬하기 위한 로직 (mid <= end인 경우 아래 로직을 따르면 정렬이 됨)
   • mid가 2인 경우 end와 교체, end는 1 감소
   • mid가 0인 경우 start와 교체, start, mid 1 증가
   • mid가 1인 경우 mid 1 증가

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let [start, mid, end] = [0, 0, nums.length - 1];

    while (mid <= end) {
        if (nums[mid] === 2) {
            [nums[mid], nums[end]] = [nums[end], nums[mid]];
            end--;
        } else if (nums[mid] === 0) {
            [nums[mid], nums[start]] = [nums[start], nums[mid]];
            start++;
            mid++;
        } else {
            mid++;
        }
    }
};

---

결론

3개의 기준점 (start, mid, end 포인터)를 이용해 0, 1, 2를 구분하는 방식으로 해결