[Array] MoveZeros

moveZeros 문제는
[0,5,0,7,6,3] 라는 배열이 주어졌을때 0을 전부 끝단으로 보내서 [5,7,6,3,0,0] 이라는 배열을 만드는 문제입니다. 여기서 중요한건 0을 제외한 5,7,6,3의 순서를 그대로 유지해야 합니다.

1. 버블 정렬로 0을 만날때마다 뒤로 미루는 방법 => 시간 복잡도O(n * 0 개수)라서 만약 0이 극단적으로 많다면 n^2과 다를게 없음.

2. 스왑을 하는것이 아니라 엘레멘트를 복사하는 방법. 선형 탐색을 하며 0을 만날때마나 카운트를 증가시키고, 0이 아닌 수를 만나면 또 다른 배열에 복사시킨 다음, 탐색이 끝나면 카운트된 0만큼을 삽입. => 시간 복잡도 O(n)

3. 0이 아닌 숫자를 현재 0이 있는 인덱스와 스왑하는 방법. 더블 포인터를 이용해서, 항상 0을 가리키는 포인터(zeroPointer)와 0이 아닌 수를 찾는 포인터(numPointer)만든다.zeroPointer는 탐색하다가 0을 발견하면 멈추고, numPointer는 0이 아닌 수를 찾을때 까지 탐색하고, 발견한다면, zeroPointer의 인덱스내 데이터와 스왑한다.

세가지 방법정도가 있는데 우리는 이 배열안에서 스왑을 통해 문제를 해결하는 세번째 방법을 살펴보겠습니다.
세번째 방법은 사실 굳이 스왑을 하지 않고 복사(덮어쓰기)를 해도 괜찮아요. (스왑보다 복사(덮어쓰기)가 비용이 덜 들기 때문에 좋음)

다시 보면 zeroPointer는 아까와 같고, numPointer는 0이 아닌 수를 발견할때마다 zeroPointer 인덱스에 복사해서 덮어쓰고, numPointer의 탐색이 먼저 끝나기 때문에 뒤에있는 zeroPointer는 나머지 인덱스에 전부 0을 써줘요.

구현
예시 [1,3,4,0,0,0,5,0]

static void Swap<T>(ref T lhs, ref T rhs)
{
    T temp;
    temp = lhs;
    lhs = rhs;
    rhs = temp;
}

static int[] moveZerosSwap(int[] nums)  //스왑을 이용한 방법
{
    int zidx = 0; //zeroPointer
    for (int nidx = 0; nidx < nums.Length; nidx++)  //nidx = NumPointer
    {
        if (nums[nidx] != 0)
        {
            Swap(ref nums[zidx], ref nums[nidx]);
            zidx++;
        }
    }
    return nums;
}

static int[] moveZerosCopy(int[] nums)  //복사를 이용한 방법
{
    int zidx = 0; //zeroPointer
    for (int nidx = 0; nidx < nums.Length; nidx++)  //nidx = numPointer 
    {
        if (nums[nidx] != 0)
        {
            nums[zidx] = nums[nidx];
            zidx++;
        }
    }

    for (; zidx < nums.Length; zidx++)  //제로 포인터가 남은 부분을 0으로 채운다.
    {
        nums[zidx] = 0;
    }

    return nums;
}