c++ leet code medium Color sort problem

color sort는 

std::vector<int> nums = {1,0,0,1,1,2,0,1,2,2,0,1,2,0,1}; 과 같은 배열을

{0,0,0,0,0,1,1,1,1,1,1,2,2,2,2}와 같이 분할한다.

 

O(n)이 복잡도로 한번 풀어본다.

코드 >>

#include <iostream>
#include <vector>
 
void color_sort(std::vector<int>& nums)
{
    int idx0 = 0;
    int idx1 = 0;
    int idx2 = (int)nums.size()-1;
    
    while (idx1 <= idx2)
    {
        while(nums[idx1]==1)
        {
            idx1++;
        }
        while(nums[idx2]==2)
        {
            idx2--;
        }
        if (nums[idx1]==0) // 어차피 while(nums[idx1]==1) 에서 1이 아닌 것 까지 idx1 이 옮겨짐
        {
            int tmp = nums[idx1];
            nums[idx1] = nums[idx0];
            nums[idx0] = tmp;
            idx0++;
            idx1++;
        }
        else
        {
            int tmp = nums[idx2];
            nums[idx2] = nums[idx1];
            nums[idx1] = tmp;
        }
        
        
    }
}
 
int main()
{   
    std::vector<int> nums = {1,0,0,1,1,2,0,1,2,2,0,1,2,0,1};
    color_sort(nums);
    for (const auto& num : nums)
    {
        std::cout << num << std::endl;  
    }
    std::cout<<"Hello World" << std::endl;
 
    return 0;
}
 

쉬운 코드 >>

#include <iostream>
#include <vector>
 
void color_sort(std::vector<int>& nums)
{
    int idx0 = 0;
    int idx1 = 0;
    int idx2 = (int)nums.size()-1;
    
    while (idx1 <= idx2)
    {
        if (nums[idx1]==0){
            int tmp = nums[idx0];
            nums[idx0] = nums[idx1];
            nums[idx1] = tmp;
            idx1++;
            idx0++;
        }
        else if (nums[idx1]==2)
        {
            int tmp = nums[idx1];
            nums[idx1] = nums[idx2];
            nums[idx2] = tmp;
            idx2--;
        }
        else
        {
            idx1++;
        }
        
    }
}
 
int main()
{   
    std::vector<int> nums = {1,0,0,1,1,2,0,1,2,2,0,1,2,0,1};
    color_sort(nums);
    for (const auto& num : nums)
    {
        std::cout << num << std::endl;  
    }
    std::cout<<"Hello World" << std::endl;
 
    return 0;
}