move zeros

• Reference
• 배열을 바라보는 관점을 높여주는 문제다.

Algorithm

• 제목만 보면 0을 움직여야만 할 것 같지만, 이렇게 생각하면 Bubble swap을 해줘야하므로 굉장히 많은 Operation이 수행된다.
• 다르게 생각해보면 숫자를 왼쪽으로 몰아주고, 0을 오른쪽으로 몰아주면 된다.
• 여기서 투 포인터 개념이 사용된다.

0 5 0 7 6 3

• 이 배열을 move zero를 하면

5  7  6  3  0  0

• 위 처럼 나와야한다. 어떻게 해야할까 ?

0  5  0  7  6  3
p1p2

• 두 개의 포인터를 begin 부터 둔다.
• p1은 숫자가 들어올 위치를 가리키는 pointer, p2는 0인지 아닌지를 이동하며 판별하는 pointer 라는 역할을 부여한다.

0  5  0  7  6  3 // Compare
p1 p2

5  0  0  7  6  3 // Swap
p1 p2

5  0  0  7  6  3 // Move
  p1p2

• 1차 예시다.

5  0  0  7  6  3
  p1p2

5  0  0  7  6  3
  p1  p2
  
5  0  0  7  6  3
  p1     p2
  
5  7  0  0  6  3
  p1     p2
  
5  7  0  0  6  3
     p1  p2

• 이후는 다음과 같이 진행된다. 이정도만 기록해도 이해하는데 충분할 것 같다.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

void moveZeros(std::vector<int> &v)
{
    auto iter1 = v.begin();

    for (auto iter2 = v.begin(); iter2 != v.end(); ++iter2)
    {
        if (*iter2 != 0)
        {
            std::iter_swap(iter1, iter2);
            ++iter1;
        }
    }
}

int main()
{
    std::vector<int> v = {0, 5, 0, 7, 6, 3};

    moveZeros(v);

    for (int e : v)
        std::cout << e << std::endl;

    return 0;
}

5
7
6
3
0
0