LeetCode 75 - Sort Colors (Medium)

문제

LeetCode - 75번

풀이 과정

0, 1, 2 로 구성되어 있는 배열을 O(n) 의 시간 복잡도와 O(1) 의 공간 복잡도를 통해 정렬하는 방법을 찾는 문제입니다.

처음에 어떻게 접근해야할지 감을 못잡아서 다른 사람의 풀이에 힌트를 얻어 해결할 수 있었습니다.
가장 중요한 것은 0 을 왼쪽에 2 를 오른쪽에 배치시켜야 한다는 것입니다.

따라서 배열을 순회하며 1 은 무시하고 0 과 2 를 만나면 들어갈 다음 위치를 가리키는 두 개의 포인터를 통해
위치를 변경해주면 O(n) 에 해결할 수 있습니다.

이때 주의할 점은 2 를 바꿀때인데 2를 swap 할 경우 0, 1, 2 중 하나의 숫자가 바뀐 위치로 오게 되는데,
여기서 walker 를 그대로 증기시켜버리면 경우에 따라서 정렬이 다 끝나지 않고 다음 위치로 옮겨지게 됩니다.

이 점에 유의하여 2 를 swap 할 경우에는 walker 를 바로 증가시켜 주지 않도록 합니다.

코드

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

  while (walker <= right) {
    if (nums[walker] === 2 && walker < right) {
      [nums[walker], nums[right]] = [nums[right], nums[walker]];
      right--;
    } else if (nums[walker] === 0) {
      [nums[walker], nums[left]] = [nums[left], nums[walker]];
      left++;
      walker++;
    } else {
      walker++;
    }
  }

  return nums;
};