[HackerRank] Counting Sort 2

https://www.hackerrank.com/challenges/countingsort2/problem

Counting Sort 2 | HackerRank

Algorithms > Sorting

 

정수 리스트가 주어지면 각 값이 등장하는 횟수를 세어 배열에 저장하고, 0이 아닌 각 인덱스의 값을 횟수만큼 출력한다.

 

 

코드

int* countingSort(int arr_count, int* arr, int* result_count) {
    *result_count = arr_count;
    int *count = malloc(100 * sizeof(int));
    int *res = malloc(arr_count * sizeof(int));
    int res_idx = 0;
    for (int i = 0; i < 100; i++) { count[i] = 0; }
    for (int i = 0; i < arr_count; i++) { count[arr[i]]++; }
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < count[i]; j++) 
            res[res_idx++] = i;
    }
    return res;
}

 

설명

횟수를 카운트하여 저장할 배열 count와 결과값을 저장할 배열 res를 각각 선언한다.

for문을 이용해 count 배열의 값을 모두 0으로 초기화하고,

초기화가 끝나면 count배열의 arr[i]번째 인덱스의 값을 증가시키며 각 숫자가 얼마나 등장하는지 카운트한다.

그리고 마지막으로 이중 for문을 이용해 count 배열의 각 인덱스의 값, 즉 빈도만큼 각 인덱스를 res 배열에 저장하고 리턴한다.