[리트코드] 75. Sort Colors

in 코딩테스트 on 리트코드




75. Sort Colors

리트코드

나의 풀이

var sortColors = function (nums) {
  return nums.sort((x, y) => x - y);
};


sort함수를 쓰면 세상 간편하지만 문제 제약조건으로 내장함수를 사용하지 말라고 했다. 

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

var sortColors = function (nums) {
  let swapped;
  for (let i = 0; i < nums.length - 1; i++) {
    swapped = false;
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1);
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return nums;
};

console.log(sortColors([2, 0, 2, 1, 1, 0]));


그래서..! 버블정렬로 구현하였다.

Runtime: 76 ms, faster than 59.45% of JavaScript online submissions for Sort Colors.


생각보다 퍼센트가 높지 않아서, 다른 사람의 코드를 살펴보자

best code

var sortColors = function(nums) {
    
    let left = 0, i = 0, right = nums.length - 1;
    const swap = (i, j) => [nums[i], nums[j]] = [nums[j], nums[i]]
    
    while(i <= right){
    
        if(nums[i] > 1){

            [nums[i], nums[right]] = [nums[right], nums[i]]
            right -= 1
        }else if (nums[i] < 1){
            // swap(i++, left ++)
            [nums[i], nums[left]] = [nums[left], nums[i]]
            left += 1
            i += 1
        }else{
          i += 1   
        }
    }
    
};