[LeetCode] 75. Sort Colors (c++)

문제의 링크는 https://leetcode.com/problems/sort-colors/ 이다.

 

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

 

문제는 굉장히 단순히 주어진 배열( 혹은 vector)를 정렬하는 문제이다.

그래서 사실 c++의 라이브러리 함수인 sort를 사용하면 한줄로 해결할 수 있는 문제이다.

 

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums.begin(),nums.end());
    }
}

하지만 문제에서 볼 수 있듯이 라이브러리 함수는 사용하지 말고 문제를 풀라고 한다.

Note: You are not suppose to use the library's sort function for this problem.

그래서 정렬 알고리즘을 직접짜서 하면 해결할 수 있는 문제지만

주어진 배열의 원소값이 0, 1, 2 즉, 3개만을 사용하는 것을 이용하면 굳이 복잡하게 정렬알고리즘을 짜지 않아도 O(n) 시간복잡도로 문제를 해결할 수 있다.

 

class Solution {
public:
    void sortColors(vector<int>& nums) {
        //sort(nums.begin(),nums.end());
        
        int Size = nums.size();
        
        int cnt0 = 0;
        int cnt1 = 0;
        
        for(int i = 0; i < Size; i++){
            if(nums[i]==0) cnt0++;
            else if(nums[i]==1) cnt1++;

        }
        
        cnt1 += cnt0;
        
        for(int i = 0; i <Size; i++){
            if(i < cnt0) nums[i]=0;
            else if(i < cnt1) nums[i]=1;
            else nums[i]=2;
        }
    }
};

결과

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sort Colors.

Memory Usage: 8.4 MB, less than 100.00% of C++ online submissions for Sort Colors.

 

* 언제나 지적과 태클을 환영입니다. 부족하지만 최대한 피드백을 반영하겠습니다.