pramp - Move Zeros To End

세번째 pramp mock interview 경험

문제

주어진 배열에서 0을 뒤로 밀어라. (https://www.pramp.com/challenge/9PNnW3nbyZHlovqAvxXW)

input:  arr = [1, 10, 0, 2, 8, 3, 0, 0, 6, 4, 0, 5, 7, 0]
output: [1, 10, 2, 8, 3, 6, 4, 5, 7, 0, 0, 0, 0, 0]

참고로 leetcode move zeros 와 동일한 문제.

해결 brute-force O(n) / O(n)

배열을 추가로 생성하고 기존 배열의 값이 0이아니면 새로 추가. 그런데 공간복잡도가 O(1)인 해결방법을 떠올리려나 머리가 반즘 하얘짐. 솔직히 쉬운 문제인데(심지어 한번 풀어본 문제) 인터뷰 상황에서 생각보다 머리가 굳음.

void moveZerosToEnd(size_t arrLength, const int arr[arrLength], int maxOutSize, int out[maxOutSize])
{
  int outcnt = 0;
  for (int i = 0; i < arrLength; i++) {
    if (arr[i] != 0)
      out[outcnt++] = arr[i];
  }
  for (int i = outcnt; i < maxOutSize; i++) {
    out[i] = 0;
  }
}

다음은 인터뷰 다 끝나고 다시 풀어본것. 참고로 아래부터는 leetcode 에서 풀었다.

해결 O(n) / O(1)

0이 아닌 값을 만나면 기존배열에 앞부터 저장. 그리고 마지막 남은 값은 그냥 0으로 채움. 이렇게하면 추가 배열이 필요없음. (예전에 이렇게 혼자 풀었었는데, 막상 인터뷰 시간에 이게 안떠올랐다! 목 인터뷰를 더 많이 해서 익숙해지는 수밖에 없음)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int retcnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0)
                nums[retcnt++] = nums[i];
        }
        for (int i = retcnt; i < nums.size(); i++)
            nums[i] = 0;
    }
};

해결 two pointer O(n) / O(1)

이 방식은 이번에 처음 풀어봤는데 더 효율적인 풀이 법이다.

기본적으로 0이 아닌 현재 배열값과 마지막 zero를 서로 swap하는것. two pointer는 각각의 포인터를 언제 increase할지를 생각하는 방식으로 접근해야함.

기본적으로 현재배열값은 증가, 0이 아닐때 마지막으로 업데이트된 zero index와 swap한다. 그때 zero index는 +1을 한다. +1만해도 되는 이유는 swap하기 직전 상황이 항상 아래와 같은데, swap을 하면 0의 index는 +1 이 되기 때문.

        nz
1 2 2 0 3 4 
      z

또는

    nz  
1 0 2 0 0 0 0 5
  z
              nz
1 2 0 0 0 0 0 5
    z

class Solution {
    void swap(vector<int>& nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
public:
    void moveZeroes(vector<int>& nums) {
        int retcnt = 0;
        int last_zero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0)
                swap(nums, i, last_zero++);
        }
    }
};