[LeetCode C++] 283. Move Zeroes

⭐️ 난이도

 

Easy

 

---

⭐️ 문제

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

Move Zeroes - LeetCode

 

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

정수형 배열 nums가 주어졌을 때, 0이 아닌 원소들의 상대적인 순서는 유지하면서 0을 끝으로 옮기시오.

 

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

단, 배열을 복사하지 않고 in-place 방식으로 해야 한다.

 

---

⭐️ Follow-up

 

Could you minimize the total number of operations done?

총 연산의 횟수를 최소화 시킬 수 있겠는가?

 

---

⭐️ Idea flow

 

문제를 읽으면서 two pointers 방식을 사용하면 어떨까? 하는 생각이 났다.

left의 초기 값은 0으로, right의 초기 값은 1로 설정한다.

left는 뒤로 보내야 할 0의 위치를 찾는 역할을, right는 앞으로 보내야 할 0이 아닌 숫자의 위치를 찾는 역할을 한다.

 

이후 경우의 수는 총 네 가지로 나뉜다.

1. left만 0일 때

   - nums[left]와 nums[right]의 값을 서로 바꾼다. 이후 left와 right의 값을 모두 1씩 증가.

2. right만 0일 때

   - 위치를 바꿀 만한 숫자가 아니므로 left와 right의 값을 모두 1씩 증가.

3. left와 right 모두 0일 때

   - right의 값만 1 증가.

4. left와 right 모두 0이 아닐 때

   - left와 right의 값을 모두 1씩 증가.

 

그렇다면 검사가 끝나는 시점은 언제인가?

right의 값이 nums의 인덱스 범위 밖을 넘어가면 그때 중단한다.

 

---

⭐️ Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        if(len == 1)    return;
        
        int left = 0, right = 1;
        while(true){
            if(right >= len)    break;
            
            if(!nums[left] && !nums[right]){ // 둘 다 0일 때
                right++;
                continue;
            }
            
            if(!nums[left] && nums[right]){ // left 값만 0일 때
                swap(nums[left], nums[right]);
            }
            left++;
            right++;
        }
    }
};

 

---

⭐️ Feedback

 

문제를 푼 후 Discuss 게시판에 가서 다른 사람들의 풀이를 보았다.

two pointers를 쓰는 사람은 거의 없었고, 대표적으로 두 가지 풀이가 있었다.

 

1. STL(stable_partition) 이용

#include<algorithm>헤더에서 제공하는 stable_partition()함수를 사용하는 방법이다.

stable_partition 함수는 매개 변수로 세 가지를 받는다.

1) 시작점,  2) 끝점,   3) 조건(return형이 bool인 함수)

 

함수의 결과가 true인 원소들은 왼쪽 파티션으로, false인 원소들은 오른쪽으로 옮겨진다.

또한 오른쪽 파티션의 시작 위치를 iterator 형식으로 return한다.

 

여기서 중요한 포인트는 stable하기 때문에 원소들의 상대적인 순서가 유지된다는 것이고,

또 다른 하나는 기존의 메모리를 점유(메모리를 추가적으로 필요로 하지 않는다 / 원소끼리 자리만 바꾼다)는 점이다.

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

 

2. without two pointers

for문을 이용해서 푸는 방법도 있었다.

여기서 정수형 변수 idx는 값이 0인 인덱스(위치)를 가리킨다.

 

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