02. LeetCode 283. Move Zeroes

LeetCode 283.  Move Zeroes

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

Move Zeroes - LeetCode

// Move Zeroes
// One Pointer is fill index
// One Pointer is find not zero
// LeetCode 283. Move Zeroes
// https://leetcode.com/problems/move-zeroes/

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

using namespace std;
void moveZeroes(vector<int>& nums)
{
	int wIdx = 0;
	for (int i = 0; i < (int)nums.size(); i++)
	{
		if (nums[i] != 0)
		{
			swap(nums[wIdx], nums[i]);
			wIdx++;
		}
	}
	fill(nums.begin() + wIdx, nums.end(), 0);
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	vector<int> nums = { 0, 1, 0, 3, 12 };
	moveZeroes(nums);
	for (auto& e : nums)
		cout << e << " ";

	return 0;
}

MoveZeroes는 배열을 포인터 하나로 순회하는 것이 아닌 또다른 순회 포인터를 이용해서 Swap 하는 Idea에서 출발한다.

 

Two Pointers의 기본 예제라고 생각한다.

 

일반 숫자를 다 옮기고 나면 wIdx는 모든 숫자가 0이 없을 경우에는 끝에 올 수도 있고

 

그 외에는 배열의 한 가운데 남게 된다.

 

값을 swap했기에 뒤에 남은 것이 항상 0이라는 보장이 없으므로 wIdx -> end 까지 0으로 채워주는 것으로 마무리 할 수 있다.

 

1. 시작점을 wIdx로 하나 더 둔다.

2. 배열을 순회하며 0이 아닌 값이면 wIdx와 교환하고 wIdx++를 진행한다.

3. 배열 순회가 종료되면 나머지를 0으로 fill 한다.