LeetCode 283 - Move Zeroes (Medium)

문제

LeetCode - 283번

풀이 과정

정렬을 수행한 뒤에 같은 키 값을 가지는 원소들의 순서가 뒤바뀌지 않는 것을 stable sort 라고 합니다.

이번 문제에서는 주어진 배열에서 0을 배열의 끝쪽으로 옮겨주되 그 순서가 뒤바뀌면 안되는 로직을 구현하였습니다.
이때 별도의 array 를 복사하여 구현하면 안되고 배열 내에서 정렬이 in-place 로 수행되어야하므로 삽입정렬을 활용하여 구현했습니다.

삽입 정렬 은 배열의 끝 원소부터 하나씩 자신의 위치를 찾아 삽입 해주는 방식을 사용하는데,
여기서는 0을 발견할 때마다 0이 위치할 수 있는 위치를 반복해서 찾음으로서 O(N^2) 의 시간 복잡도로 문제를 해결하였습니다.

코드

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