[HackerRank] Sorting > Closest Numbers

https://www.hackerrank.com/challenges/closest-numbers/problem

배열 값에서 차가 가장 작은 수를 출력하면 된다. (중복 허용)

 

배열을 오름차순으로 정렬한 뒤 다음 원소와의 차를 구해 가장 작은 값을 배열에 넣어줬다.

int compare(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
int* closestNumbers(int arr_count, int* arr, int* result_count) {
    qsort(arr, arr_count, sizeof(int), compare);
    int *diff = (int*)malloc(sizeof(int)*(arr_count-1)*2);
    int dif = 0, min = 0, flag = 0;
    if(arr[0] > arr[1]){
        min = arr[0] - arr[1];
        diff[0] = arr[1];
        diff[1] = arr[0];
    }
    else {
        min = arr[1] - arr[0];
        diff[0] = arr[0];
        diff[1] = arr[1];
    }
    for(int i=1; i<arr_count-1; i++){
        if(arr[i] > arr[i+1]){
            dif = arr[i] - arr[i+1];
            if(min > dif){
                min = dif;
                flag = 0;
                diff[flag] = arr[i+1];
                diff[++flag] = arr[i];
            }else if(min == dif){
                diff[++flag] = arr[i+1];
                diff[++flag] = arr[i];
            }
        }else{
            dif = arr[i+1] - arr[i];
            if(min > dif){
                min = dif;
                flag = 0;
                diff[flag] = arr[i];
                diff[++flag] = arr[i+1];
            }else if(min == dif){
                diff[++flag] = arr[i];
                diff[++flag] = arr[i+1];
            }
        }
        
    }
    *result_count = flag+1;
    return diff;
}

정렬은 <stdlib.h>에 있는 qsort를 사용했다.

https://dojang.io/mod/page/view.php?id=638

 

qsort 정렬을 사용하기 위해 compare함수를 선언하고 arr을 정렬했다.

답을 저장할 diff를 선언하고 사이즈를 (arr_count-1)*2로 설정했다. 모든 원소의 차가 같다고 하면 쌍이 arr_count-1만큼 나오니까 그 두배를 배열 크기로 설정한 것이다.

dif는 for문을 돌면서 구할 차, min은 최소인 차, flag는 diff의 인덱스 값이다.

min에는 arr[0]과 arr[1]을 먼저 넣어주고 for문을 돌려 dif가 min보다 작으면 diff에 갱신되도록 했다. 지금 생각해보니까 최소를 구할 때마다 diff를 초기화해줬어야 했는데 테스트케이스에 최소가 아닌 차가 여러 개 있는 경우는 없었나보다.

flag는 min이 중복될 때 diff에 원소를 추가해주기 위해 인덱스 값으로 사용했다.

result_count는 diff에 들어간 원소 개수와 같아야 하므로 flag+1로 넣어줬다.