75. Sort Colors

💡풀이

Discussion에서 아래의 방법으로 푼 분이 올린 그림이다.

// Discussion
// 나중에 다시 풀어봐야할 문제
function sortColors(nums) {
  let low = 0;
  let high = nums.length - 1;

  for (let i = 0; i <= high; i++) {
    if (nums[i] === 0) {
      [nums[i], nums[low]] = [nums[low], nums[i]]; // swap
      low++;
    } else if (nums[i] == 2) {
      [nums[i], nums[high]] = [nums[high], nums[i]];
      high--;
      i--; 
    }
  }
}

// 비슷한 풀이
var sortColors = function(arr) {
    
    let low=0, mid=0, high=arr.length-1


    while ( mid <= high ) { 
    
        if( arr[mid] == 0 ){ 
            swap( low, mid ); 
            mid++; 
            low++ ;
        } 
    
        else if( arr[mid] == 1 ) {   
            mid++ ;  
        } 


        else if( arr[mid] == 2 ) {
            swap( mid,high ); 
            high--  
        } 
    }


    function swap(a,b) {
        [arr[b], arr[a]] = [arr[a], arr[b]]
    }


};

📝정리

• O(N)의 시간복잡도와 O(1)의 공간복잡도로 풀 수 있는지(정렬할 수 있는지) 물어보는 문제였다. 정렬 알고리즘을 더 공부해야 할 듯.

문제 링크

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

LeetCode GitHub

https://github.com/tTab1204/LeetCode/tree/main/%EC%A3%BC%EC%98%81