[C++] LeetCode : Sort Colors

Question

배열 nums 와 red, white, blue로 이루어진 n개의 객체들이 있을 때, 해당 객체들을 같은 color끼리 인접하게 in-place로 정렬하라. 반드시 sort 라이브러리를 쓰지않고 정렬해야한다.

 

제약사항

• n 은 nums.length() 와 같다
• n은 최소 1 ~ 최대 300이다.
• nums[i] 는 0,1, 2 중 하나이다.
  
  

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

  모든 숫자를 한번 씩 확인해봐야 하기 때문에 n을 배열의 길이라 했을 때, BCR은 O(n) 이다

 

고려사항

1. 빈 배열일 경우 (제약사항엔 1~300이지만, 고려해본다) 

Solution1 - Bruth Force 

  단순한 방법은 그냥 잘 알려진 정렬 라이브러리를 사용해서 정렬 하는 것이다. 다만 문제에서 정렬을 제한하였고 시간복잡도 또한 O(nlogn)이기 때문에 이 솔루션은 패스한다. 

 

Solution1 - Counting Sort

 문제를 읽자마자 해당 정렬 방법이 떠올랐다. Counting Sort는 빈도수를 이용한 방법이다. 나오는 숫자의 범위가 일정할 때 유용한 정렬 방법이다. 해당 정렬을 사용하면 O(n) 에 해결할 수 있다.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3] = {0};
        for(auto num : nums){
            count[num]++;
        }
        for(int i=0,j=0; i<nums.size();){
            if(count[j] > 0) {
                nums[i++] = j;
                count[j]--;
            }
            else{
                ++j;
            }
        }
    }
};

• Time complexity : O(n) // nums안의 수를 확인 + 덮어씌우는 작업 으로 총 O(2n)으로 O(n)이다.
• Space Complexity : O(1)  // 일반적인 Counting 정렬이라면 Counting을 위한 공간이 필요하지만, 보통 상수공간이다. 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/798/

Explore - LeetCode

* 본 포스트 관련된 토의, 지적 및 조언은 모두 환영합니다