[Two Pointers][Easy] 283. Move Zeroes

https://leetcode.com/problems/move-zeroes

Move Zeroes - LeetCode

 

Q. 배열에 등장하는 0을 모두 뒤로 옮기도록 배열을 재 구성하라.

 

우선 직관적으로 0이 등장하면, 뒤로 옮기고, 0이 존재하는 곳으로 모든 값을 당길 수 있다. 

하지만, 아래 보는바와 같이 옮기는 연산때문에 O(N^2) 의 TC가 소요되므로, 바람직하지 않다.

void moveZeroes(vector<int>& nums)
{
    int cntFound = 0;
    for (int k = 0; k < nums.size(); ++k)
    {
    	// 0 을 뒤로 옮긴 위치에 도달하면, 연산 완료.
        if (k >= nums.size() - 1 - cntFound)	
        	break;

        if (nums[k] == 0)
        {
            // 뒤에서 현재까지 배열을 당긴다. 
            for (int q = k; q < nums.size() - 1 - cntFound; ++q)
                nums[q] = nums[q + 1];
            
            // 그리고 뒤자리엔 0을 채운다.
            nums[nums.size() - 1 - cntFound++] = 0;
            
            // 이 당긴 위치에 또 0 이 등장할수 있으므로, 이 위치 재계산.
            --k;
        }
    }
}

 

 

더 간단하게 생각해보자, 0을 가장 뒤편으로 이동하기만하면 되지, 0이 어디서 왔는지 기억할 필요가 없다.

따라서 순서대로 0 인 값을 제외하고 모두 앞쪽으로 몰고, 이후 나머지는 모두 0으로 쓴다.

void moveZeroes(vector<int>& nums)
{
    int zero = 0;
    for (int k = 0; k < nums.size(); ++k)
    {
        if (nums[k] == 0)
        {
            ++zero;	// 0인 녀석을의 개수는 알 필요가 있다.
            continue;
        }
        // 0 이 아닐 때, 순서대로 앞에다 옮긴다. 
        nums[k - zero] = nums[k];
    }
    // 이제 남은 위치부터는 모두 0 이다. 
    for (int k = nums.size() - 1 - zero; k < nums.size(); ++k)
        nums[k] = 0;
}

 

이렇게 하면, O(N)의 TC에 in place로 연산을 처리 할수 있겠다.