[Javascript] LeetCode 283. Move Zeroes

[Javascript] LeetCode 283. Move Zeroes

💡 구글에 Javascript 풀이가 많이 없거나, 배운 점이 있으면 포스팅합니다.

내 풀이

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {    
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            changePosition(nums, i);
        }
    }
};

let changePosition = (nums, i) => {
    for (let j = i + 1; j < nums.length; j++) {
        if (nums[j] !== 0) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            return;
        }
    }
}

• 1) for문으로 0을 찾는다.
• 2) 0이면 그 다음 숫자부터 0이 아닌 놈을 찾아서, 자리를 바꾼다.
• 3) 반복
• ⇒ O(n!)의 냄새가 난다. 더 좋은 풀이가 있을 것 같다.

다시 푼 풀이

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {    
  let nonZeroIdx = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[nonZeroIdx] = nums[i];
      nonZeroIdx++;
    }
  }

  for (let i = nonZeroIdx; i < nums.length; i++) {
    nums[i] = 0;
  }

};

• 1) 이면 Skip하고, 0이 아니면 배열에 차례대로 적어준다.
• 2) nonZeroIdx부터 마지막까지 0으로 채워준다.
• ⇒ O(n) 솔루션!

배운 점, 느낀 점

• 예전에 풀어본 문제지만 처음부터 좋은 풀이가 나오지 않았다. 항상 조금 더 좋은 방법으로 풀 수 있도록 연습해야겠다.
• LeetCode는 프로그래머스나 백준처럼 return 값만 맞으면 되는게 아니라, return 없이 주어진 인풋이 참조하고 있는 데이터 자체를 변형해야 한다. 그 부분은 조금 더 까다롭다. 대신 공간 복잡도 측면에서 훨씬 좋은 코드가 나온다.