[LeetCode] 75 Sort Colors JavaScript

문제 링크

Sort Colors - LeetCode

 

문제 유형

정렬, 브루트 포스, in-place sort algorithm

 

문제 풀이

이 문제는 아래의 다양한 방식으로 접근할 수 있다.

• 정렬 메서드 sort() 사용하기
  javascript 엔진 v8에서는 삽입 정렬과 병합 정렬을 합친 TimSort를 사용해 정렬 메서드를 구현한다고 한다. 따라서, sort() 메서드를 사용해 정렬을 하였을 때, O(nlogn)의 시간 복잡도를 갖는다.
  
  
• 각 숫자의 개수를 센 후 개수 만큼 숫자 나타내기
  배열을 순차적으로 접근해 0(red), 1(white), 2(blue)의 개수를 세고, 차례대로 개수만큼 해당 숫자를 배열 내에 출력해주면 된다.
  따라서, O(n)의 시간복잡도를 갖는다.
  
  
• in-place, swap
  in-place 란 추가적인 메모리 할당 없이 주어진 메모리 자체에서 작업을 수행하는 방식을 말한다. 따라서, in-place한 알고리즘은 Not in-place한 알고리즘보다 공간복잡도가 낮다.
  
  퀵 정렬을 할 때는 in-place 정렬이 가능하다. 퀵 정렬은 피벗(Pivot)과 분할(Partitioning)을 이용해 정렬을 하는 방식이다.
  퀵 정렬의 분할 방법은 다음과 같다.
  포인터는 피벗과 비교할 요소의 위치를 가리키는 포인터 1과 피벗보다 작은 요소가 올 위치를 가리키는 포인터 2가 있다.
  1. 포인터 1이 가리키는 현재 요소가 피벗보다 작다면 포인터 2와 swap하고, 포인터 2를 한칸 앞으로 옮긴다.
  2. 이를 반복하여 포인터 2가 포인터 1의 왼쪽에 있다면 이동을 중지한다.
  3. 피벗의 왼쪽에는 피벗보다 작은 요소들이, 피벗의 오른쪽에는 피벗보다 큰 요소들이 분할된다.
  
  퀵 정렬의 분할과 비슷하게 이 문제를 해결한다.
  1. 빨간색, 파란색 포인터는 배열의 맨 처음, 초록색 포인터는 배열의 맨 끝으로 포인터 3개를 초기화한다.
  2. 초록색 포인터가 빨간색 포인터를 역전할 때까지 다음의 과정을 반복한다.
       2-1. 빨간색 포인터가 0을 만나면 파란색 포인터와 swap하고, 파란색 포인터와 빨간색 포인터를 한칸 앞으로 이동시킨다.
       2-2. 빨간색 포인터가 2를 만나면 초록색 포인터와 swap하고, 초록색 포인터를 한칸 뒤로 이동시킨다.
       2-3. 빨간색 포인터가 1을 만나면 아무런 과정 없이 빨간색 포인터를 한칸 앞으로 이동시킨다.
  최종적으로, 파란색 포인터 앞에는 0이 있고, 초록색 포인터 뒤에는 2이 있고, 그 사이에는 1이 있어 정렬된다.
  이는, O(n)의 시간복잡도를 갖게 된다.
  
  포인터를 3개 사용해 빨간색 포인터를 각각의 포인터와 swap 후에 파란색 포인터는 앞으로 한칸 이동하고, 초록색 포인터는 뒤로 한칸 이동해 파란색 포인터 앞에는 0만 오고, 초록색 포인터 뒤에는 2만 오도록 유지하는 것이 핵심이다.

 

코드

// in-place sort algorithm
var sortColors = function(nums) {
    let idx0 = 0;
    let idx2 = nums.length - 1;
    let i = 0;
    
    while (i <= idx2) { // 초록색 포인터가 빨간색 포인터를 역전할 때까지 반복
        if (nums[i] === 0) {
            [nums[idx0], nums[i]] = [nums[i], nums[idx0]];
            idx0++;
            i++;
        } else if (nums[i] === 2) {
            [nums[i], nums[idx2]] = [nums[idx2], nums[i]];
            idx2--;
        } else {
            i++;
        }
    }
    
    return nums;
};

 

참고

https://www.youtube.com/watch?v=VJWUWolxHu0&list=PLDV-cCQnUlIYFOXYzqLoXnEye4WxDa_30&index=6

https://woong-jae.com/javascript/220412-sort-implementation

https://modoocode.com/248