[LeetCode] 283. Move Zeroes c++

• 문제

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.

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

 

• 문제 해결

처음에는 벡터 원소에 0이 있으면 삭제하는 문제인 줄 알았다.

remove_if() 함수를 사용해서 0이라면 삭제하는 코드를 작성했다.

class Solution {    
   
public:        
    static bool oper(const int& a){
        if( a == 0){
            return true;
        }
        return false;
    }
    void moveZeroes(vector<int>& nums) {
        nums.erase(remove_if(nums.begin(), nums.end(), oper), nums.end());
        return;
    }
};

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

0을 삭제하지 않아야 하는데 삭제해서 문제와 맞지 않는 코드이다.

 

0을 삭제하지 않고 오름차순으로 정렬되도록 코드를 작성했다.

class Solution {    
   
public:        
    static bool cmp(const int& a, const int& b){
        if(a == 0){
            return a > b;
        }
        if(b == 0){
            return a > b;
        }
        return a < b;
    }
    
    void moveZeroes(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        return;
    }
};

//Input: nums = [2, 1]
//Output: [1, 2]
//Expected : [2, 1]

0은 삭제하지 않지만 오름차순으로 정렬하는 코드라  문제와 맞지 않는 코드이다.

배열의 순서는 보장하고, 0은 맨뒤로 이동시켜야 한다.

 

 

재시도!

class Solution {    
   
public:
    static bool oper(int a){
        if ( a == 0){
            return true;
        }
        return false; 
    }
    
    void moveZeroes(vector<int>& nums) {    
        int cnt = count(nums.begin(), nums.end(), 0);
        nums.erase(remove_if(nums.begin(), nums.end(), oper), nums.end());
        for(int i = 0; i < cnt; i++){
            nums.push_back(0);
        }
        return;
    }
};

 

드디어 성공!

nums 배열의 0의 개수를 확인하고 nums 배열에 있는 0을 모두 삭제한다.

nums배열에 있던 0의 개수만큼 nums배열의 맨 뒤에 0을 삽입한다.

 

 

다른 방법1

  void moveZeroes(vector<int>& nums) {
        
         for(int i = 0, next = 0; i < nums.size(); ++i){
             if(nums[i]){
                swap(nums[i], nums[next++]);
             }
         }
        
        return;
    }

 

다른 방법2

void moveZeroes(vector<int>& nums) {
        
     stable_partition(begin(nums), end(nums), [](int i){return i;});
        
      return;
 }

stable_partition 함수에 대한 설명은 아래 포스팅에 되어있습니다~

 

2022.12.24 - [Programming/c++] - [c++] std::stable_partition

[c++] std::stable_partition

 

 

다른 방법3

    void moveZeroes(vector<int>& nums) {
        
        stable_partition(rbegin(nums), rend(nums), logical_not<int>());
        
        return;
    }

reverse begin, reverse end 역방향 반복자를 지정해서 logical_not<int>() 결과가 false인 요소는 맨 뒤로 이동합니다.

logical_not<int>() 은 인수에 대해 논리 not연산을 수행하는 미리 정의된 함수 개체입니다.