75. Sort Colors

💡 풀이

// 첫 번째 풀이
function sortColors(nums) {
  let isZero = 0;
  let isTwo = nums.length - 1;
  let i = 0;

  while (i <= isTwo) {
    let num = nums[i];

    if (nums[i] === 0) {
      nums[i] = nums[isZero];
      nums[isZero] = num;
      isZero++;
      i++;
    } else if (nums[i] === 2) {
      nums[i] = nums[isTwo];
      nums[isTwo] = num;
      isTwo--;
    } else i++;
  }
  console.log('nums:', nums);
  return nums;
}

let nums = [2, 0, 2, 1, 1, 0];
sortColors(nums);

// 만약 swap되는 부분을 함수로 따로 빼고 싶다면
const swap = (i, j) => {
  [nums[i], nums[j]] = [nums[j], nums[i]];
};

// 이런 식으로 swap 함수를 따로 작성하면 된다. 
// JS의 배열 구조분해 할당을 사용하면 매우 가독성 좋게 코드 작성이 가능하다.

📝 정리

QuickSort의 작동 방식과 매우 유사하다. in-place로, O(N)의 시간복잡도로 nums 배열을 정렬해야 했는데, 포인터 3개(isZero, isTwo, i)를 사용해 스왑을 진행하며(QuickSort) 정렬하면 O(N)의 시간복잡도와 in-place로 문제를 해결할 수 있다. 정렬 쪽을 이해하는 데 많은 도움이 된 문제였다!

• isZero : 마지막 0까지의 pivot 포인터(처음을 담당)

• isTwo : 처음 2부터의 pivot 포인터(마지막을 담당)

• i : 0, 1 을 만날때마다 지속적으로 순회하는 포인터

  수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/sort-colors/

LeetCode GitHub

https://github.com/tTab1204/LeetCode