[Leetcode] 283. Move Zeros (C++ 풀이)

정수 배열이 인자로 주어졌을 때, 0인 요소들은 우측 끝으로 모으고, 나머지 정수들은 순서를 그대로 유지하며 앞으로 당겨와야한다. 

 

example 1에서 보면, 0들은 다 뒤로 밀려나고, 나머지 정수들은 "순서 그대로" 앞으로 옮겨왔다. 최적의 방법은 아니지만, 맨 앞부터 탐색하면서 0을 만나면, 가장 가까운 0이 아닌 정수를 만나면 자리를 바꿔주면서 뒤로 밀었다.

 

 

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0;
        

        while (left < nums.size()-1){
            if(nums[left] == 0){
                
                for(int i=left+1; i < nums.size(); i++){
                    if (nums[i] != 0){
                        nums[left] = nums[i];
                        nums[i] = 0;
                        break;
                    } 
                }
            }
            left += 1;
        }
    }
};

가장 바깥 while문인 left는 앞에서부터 0을 탐색한다. 그리고 안쪽의 for문은 0이 아닌 수를 탐색하며 앞으로 당겨온다.

 

 

직관적이긴한데, 제일 앞에서 0을 만날 경우, 모든 iteration에서 operation이 일어나는 불상사가 일어나서 최적의 방법은 아니라고 볼 수 있다.