LeetCode | 283. Move Zeroes (*Two Pointers)

문제

(링크)

풀이

시행착오

const moveZeroes = function (nums) {
  let len = nums.length;
  for (let i = 0; i < len; i++) {
    if (nums[i] === 0) {
      nums.splice(i, 1);
      nums.push(0);
      len--;
    }
  }
};

케이스 [0,0,1] 일 때 [1,0,0]을 출력해야 하는데 [0,1,0]을 출력했다.
0이 연속으로 올 때 통과할 수 없는 코드였다.

통과

const moveZeroes = nums => {
  let idxArr = [];
  let cnt = 0;

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 0) {
      idxArr.push(i);
      cnt++;
    }
  }

  for (let i = 0; i < idxArr.length; i++) {
    nums.splice(idxArr[i] - i, 1);
  }

  for (let i = 0; i < cnt; i++) {
    nums.push(0);
  }
};

통과 목적으로 억지로 풀었지만 마음에 들지 않았다.
leetcode에서 투 포인터 알고리즘을 사용해보라는 힌트가 있길래
고민하다가 다른 풀이를 참고해보았다.

참고

O(N) time & O(1) space 풀이 1. (링크)

const moveZeroes = nums => {
  let index = 0;

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

    if (num !== 0) {
      nums[index] = num;
      index++;
    }
  }

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

0이 아닌 숫자를 만날 때마다 1씩 증가시킨 index부터 for문을 돌아서 0으로 바꿔준다.

O(N) time & O(1) space 풀이 2. (링크)

const moveZeroes = nums => {
  for (let i = 0, j = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      const temp = nums[i];
      nums[i] = nums[j];
      nums[j++] = temp;
    }
  }
};

for문 안에서 i, j 변수 두 개를 만들고, 0이 아닌 숫자일 경우 해당 숫자(temp)와 0의 위치(j)를 바꿔준다.
j는 0이 아닌 경우에만 1씩 증가해서 가장 앞에 있는 0의 인덱스를 기억한다.