(Leet Code c++)Move Zeroes

283. Move Zeroes

 

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

 

Example 1:

Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

Example 2:

Input: nums = [0] Output: [0]

 

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

주어진 nums에 있는 모든 0을 맨 뒤로 옮기는 작업을 해야 한다.

스택과 0의 개수를 세는 카운팅 변수를 이용했다.

 

우선 nums를 뒤에서부터 접근을 한다.

0이 아닌 수들은 스택에 저장한다.

만약 0이라면 카운팅을 늘려준다.

공통적으로는 nums에 있는 수를 제거한다.

 

이제 스택이 빌 때까지 while문 실행!

nums에 다시 0이 아닌 수를 옮겨 주도록 한다.

 

스택이 비어진다면 0의 개수만큼 다시 nums 뒤에 넣어주면 끝!

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        stack<int> stk;
        int cnt = 0;
        
        for(int i = nums.size() - 1; i >= 0; i--){
            if(nums[i] != 0){
                stk.push(nums[i]);
            }
            else{
                cnt++;
            }
            
            nums.pop_back();
        }
        
        while(!stk.empty()){
            nums.push_back(stk.top());
            stk.pop();
        }
        
        while(cnt--){
            nums.push_back(0);
        }
    }
};