[LeetCode] 283. Move Zeroes

LeetCode - 283. Move Zeroes 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/move-zeroes/

풀이

주어진 벡터의 원소에서 0은 벡터의 제일 끝으로 보내는 문제이다. (정렬할 필요는 없다.) 벡터 라이브러리에서 제공하는 erase를 이용하였다.

원소가 제거될때마다 eraseCnt를 증가시켰고 전체 반복횟수가 제어되도록 i < N - eraseCnt를 반복조건으로 이용한다. 특정 위치에서 0을 제거하면 그 뒤에 있던 원소가 앞으로 당겨져서 인덱스가 변경되기 때문에 --i를 해주었다.

매개변수가 lvalue reference 타입이므로 별도의 반환없이 매개변수 vector를 직접 변경하면 된다.

소스 코드

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        const int N = (int)nums.size();
        int eraseCnt = 0;
        for (int i = 0; i < N - eraseCnt; ++i) {
            if (nums[i] == 0) {
                nums.push_back(0);
                nums.erase(nums.begin() + i);
                ++eraseCnt;
                --i;
            }
        }
    }
};

---

[추가] 2020. 06. 28.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int idx = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (nums[i] != 0) {
                nums[idx] = nums[i];
                ++idx;
            }
        }
        for (int i = idx; i < (int)nums.size(); ++i) {
            nums[i] = 0;
        }
    }
};