HackerRank/Counting Sort 1

문제를 잘 봐야 한다. 등장할 수 있는 숫자는 0이상 100 미만이다. 그러므로 vec의 공간은 딱 100만 잡으면 된다. 그리고 0도 출력해야 하므로 100 고정으로 잡야아 하고 동적으로 arr.size() 처럼 이상한걸 잡을 필요가 없다.

추가로, Counting Sort를 완성하려면 이제 저 빈도수를 저장한 ret을 순회하면서 해당 숫자의 빈도수만큼 다른 vec에 저장시키면 된다. 1이 3번, 2가 2번 섞여서 등장하는 배열이 있다면 1이 3번 2가 2번 있으므로 11122 이렇게 출력해주면 된다. 이게 Couting Sort 이다.

vector<int> countingSort(vector<int> arr) {
    vector<int> ret(100, 0);
    
    for(int i=0; i<arr.size(); ++i)
    {
        ret[arr[i]]++;
    }
    
    return ret;
}