[c++/LeetCode-Array] 75. Sort Colors

 

 

난이도: Medium

키워드: Array

 

 

문제

주어진 배열 nums에는 빨간색, 흰색 또는 파란색으로 색칠된 n개의 객체가 있습니다. 이들을 그 자리에서 정렬하여 동일한 색상의 객체가 서로 인접하도록 만듭니다. 이때 색상은 빨간색, 흰색 및 파란색 순서로 배열됩니다.

빨간색, 흰색 및 파란색을 각각 나타내기 위해 정수 0, 1 및 2를 사용할 것입니다.

라이브러리의 정렬 함수를 사용하지 않고 이 문제를 해결해야 합니다.

 

문제 원문: https://leetcode.com/problems/sort-colors/description/

 

 

문제 풀이

 

• 색상 개수가 많지 않으니까 target 색상을 바꿔가면서 sorting을 하자
• in_place 로 sorting을 해야하니까, swap해야할 index를 기억해가면서 swap하는 알고리즘을 짜자.
• 현재 색상으로 swap할 공간을 찾고, 그다음 swap할 index를 찾는 방식으로 문제 해결

 

Runtime: 0ms Beats100.00%of users with C++

Memory: 9.88MB Beats32.94%of users with C++

 

 메모리는 color 값 벡터때문인듯, 그냥 3 이하일때까지로 loop를 수정하면 swap 용 메모리만 사용하니까 좀 더 최적화 가능.

class Solution {
public:
    void sortColors(vector<int>& nums) {

        vector<int> colors={0,1,2};
        int last_idx = 0;

        for(auto color: colors){
            for(int i = 0; i < nums.size(); ++i){
                if(nums[i] == color){
                    auto swp = nums[last_idx];
                    nums[last_idx++] = nums[i];
                    nums[i] = swp;
                }
                // update last_idx
                while(last_idx < nums.size() && nums[last_idx] < color){
                    last_idx++;
                }
            }
        }

    }
};