Leetcode - 1331. Rank Transform of an Array

문제

주어진 배열값을 랭킹으로 변환해서 리턴하라 (크기 작은 순)
https://leetcode.com/problems/rank-transform-of-an-array/

Input: arr = [40,10,20,30]
Output: [4,1,2,3]

해결

링크드 리스트 기반 해시테이블을 생성해서 풀었는데 많이 느리다. (Runtime: 249 ms, faster than 18.75%)

    for (int i = 0; i < arrSize; i++)
        if (lookup(arr_sort[i], rank, CREATE)->rank == rank)
            rank++;

arr_sort[] 의 중복된 값은 rank를 유지, 하고 바뀐 값부터 rank를 증가시키는 부분. (개인적으로 간결하고 기발했다고 생각.). 예를 들어 [2,2,5,9] 이 주어진다고 할때, rank에 그냥 i값을 저장하면 답이 [1,1,2,3] 으로 나와야하는데, [1,1,3,4]가 되어버림.

#define HSIZE 4093

struct elem {
    int num;
    int rank;
    struct elem *next;
};
struct elem *table[HSIZE];

unsigned int hash(int key)
{
    return (unsigned int)key % HSIZE;
}

enum {
    SEARCH = 0,
    CREATE
};
struct elem *lookup(int val, int rank, int create)
{
    unsigned int hval = hash(val);
    struct elem *node = table[hval];
    for (; node != NULL; node = node->next)
        if (node->num == val)
            return node;
    if (create) {
        node = (struct elem *)malloc(sizeof(struct elem));
        node->num = val;
        node->rank = rank;
        node->next = table[hval];
        table[hval] = node;
    }
    return node;
}

int cmp(void *a, void *b)
{
    return *(int *)a - *(int *)b;
}

int* arrayRankTransform(int* arr, int arrSize, int* returnSize){
    int *arr_sort = (int *)malloc(sizeof(int) * arrSize);
    int rank = 1;
    
    memset(table, 0, sizeof(struct elem *) * HSIZE);
    memcpy(arr_sort, arr, sizeof(int)*arrSize);
    qsort(arr_sort, arrSize, sizeof(int), cmp);
    
    for (int i = 0; i < arrSize; i++)
        if (lookup(arr_sort[i], rank, CREATE)->rank == rank)
            rank++;
    for (int i = 0; i < arrSize; i++)
        arr[i] = lookup(arr[i], 1, SEARCH)->rank;
    
    free(arr_sort);
    *returnSize = arrSize;
    return arr;
}