[LeetCode] 75. Sort Colors

LeetCode - 75. Sort Colors 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/sort-colors/

풀이

매개변수 nums는 정수를 가지고 있고, 그 정수는 {0, 1, 2} 중에서 하나다.

이 숫자를 오름차순으로 나타내는 문제인데, Follow up이 있다.

Follow up:

• 정렬 라이브러리를 사용하지 않고 해결
• One-pass algorithm과 의 space complexity
  • One-pass algorithm : 이하의 시간복잡도와 공간복잡도

문제 조건에서 찾아야 할 값이 {0, 1, 2} 3개 밖에 없으므로 계수 정렬(counting sort)을 사용하여 해결하였고 시간 복잡도는 이다.

소스 코드

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cnt[3] = {0}, idx = 0;
        for (int k : nums) {
            ++cnt[k];
        }
        for (int i = 0; i != 3; ++i) {
            for (int j = 0; j != cnt[i]; ++j) {
                nums[idx] = i;
                ++idx;
            }
        }
    }
};