logo
devhak

Move Zeroes

/LeetCode

문제 해석

요약

주어진 배열에서 나머지는 순서는 그대로 유지하면서 모든 0을 배열의 끝으로 보내여라. in-place로 구현해야한다.

전문

🇰🇷 번역

배열인 nums가 주어지면, 모든 0을 배열의 끝으로 보내는 함수를 작성하여라. 단, 0이 아닌 요소들은 모두 원래 순서를 유지해야 한다.

Input: [0,1,0,3,12] Output: [1,3,12,0,0]

주의:

  1. 배열을 복사하지 않고, in-place(추가 메모리 없이)로 구현해야한다.

  2. 총 작동(단계) 수를 최소화 하여라.(시간복잡도를 최소로 해라)

🇺🇸 원문

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Input: [0,1,0,3,12] Output: [1,3,12,0,0]

Note:

  1. You must do this in-place without making a copy of the array.

  2. Minimize the total number of operations.

🤔 문제 해결 방법 구상

  1. 모든 배열을 순회
  2. 0인 요소를 만나면 splice, 0을 push
  3. splice하면 인덱스가 꼬일 위험이 있으므로 처리해야함(i--)
  4. 또한 push를 했으므로 0을 계속 만나게 되므로 처리해야함(count)

코드 구현

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const moveZeroes = function(nums) {
  if (nums.length < 2) return nums;

  let count = 0;

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

  return nums;
};

결과 분석

Runtime: 88 ms
Memory Usage: 37.2 MB

nums 배열을 추가로 복사하지 않고 테스트를 통과하였다. 표면적으론 for문을 한 번으로 문제를 풀어서 시간 복잡도가 O(n)이라고 생각했는데, 리트코드 런타임 랭크는 낮은 편이었다. 내 생각엔 splice메소드를 사용하면서 인덱스 변화가 생기고, i를 감소시키는 등의 과정이 실제 런타임을 증가시키는 것 같다. splice메소드의 시간복잡도가 O(n)이고, 사실상 이 코드의 시간복잡도는 O(n^2)이다.

🧐 개선

Related Topics 항목을 찾아보니, Two Pointers 태그가 있었다.

Two Pointers는 말그대로 두개의 포인터를 이용한 알고리즘이다.
하나의 포인터를 기준으로 잡고, 나머지 포인터는 나아가며 루프를 돌아야 할때 사용하는 알고리즘이라고 생각하면 될 것 같다. 기억하는 포인터의 시점은, 그 앞을 더이상 살펴볼 필요가 없는 시점일 것이다.

Two Pointers를 활용하여 splice와 push 메소드 없이 코드를 작성해 보려한다.

개선 코드

  1. 이 문제에서 포인터들은 nums의 인덱스를 가리킬것이다.
  2. 첫번째 포인터(pointer)는 0인 인덱스를 기록하는 것이다.
  3. 두번째 포인터는 for문을 도는 i이다.
  4. 0이 아닌 요소를 만나면 pointer를 증가시킨다. 그리고 그 요소를 그대로 가져가면 된다. 만약 0을 만난다면, pointer는 변화 없이 i만 증가하게될 것이다. 다시 0이 아닌 요소를 만난다면, pointer와 같은 인덱스에 그 요소를 배치하고 pointer를 증가시게 되는 것이다.
  5. 배열을 모두 순회하고 나면, pointer는 0이 아닌 수들을 지나고 처음으로 0인 인덱스 값이 될 것이다. 그러므로 pointer 값부터 0을 배치하면 된다.
const moveZeroes = function(nums) {
  if (nums.length < 2) return nums;

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

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

  return nums;
}

개선 결과

Runtime: 64 ms
Memory Usage: 36.8 MB

추가 메모리 없이 작업하므로 공간복잡도는 O(1), nums의 크기에 따라 달라지므로 시간복잡도는 O(n)이다.

마무리

사용하는 메소드가 어떤 방식으로 작동하는지, 어떤 복잡도를 가지고 있는지도 생각해봐야 한다. 편리하다고 메소드를 마구 사용하다보면 코드는 조금 짧아지더라도 복잡도의 결과가 나쁠 수 있다.

Reference & Learn More

GeeksforGeeks Two Pointers Technique

Tags
Comments