[HackerRank] The Full Counting Sort

5주차 자료구조 복습 문제
Prepare > Algorithms > Sorting

풀이

Counting Sort의 응용 문제이다. Counting Sort의 알고리즘은 다음과 같다.

1. 0~n 까지의 버켓을 준비한다.
2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 버켓에 차례대로 데이터를 저장한다.
3. 0부터 차례대로 버켓에서 데이터를 다시 가져온다.
4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 과정을 반복한다.

해당 문제는 2번까지 한 뒤 원소들을 출력하면 된다. 이때 0~ 원소 개수의 절반 값은 데이터를 "-"로 바꿔주어야 한다. n은 최대 100이라고 주어졌으므로 해당 문제를 풀때 필요한 버켓을 100까지 설정하고 코드를 작성하였다.

전체적인 코드는 다음과 같다.

void countSort(vector<vector<string>> arr) {
    int cnt, maxAN, temp;
    vector<vector<string>> sortlist(100);
    
    cnt = 0;    
    for(int j=0; j<arr.size(); j++){
        temp = stoi(arr[j][0]);
        if(cnt < arr.size()/2){
            arr[j][1] = "-";
            ++cnt;
        }            
        sortlist[temp].push_back(arr[j][1]);
    }
    
    for(int i=0; i<100; i++){
        for(int j=0; j<sortlist[i].size(); j++)
            cout << sortlist[i][j] << " ";
    }
}

실행 결과는 이렇다.