Leetcode - 1282. Group the People Given the Group Size They Belong To

문제

i번 사람이 포함된 그룹 크기가 groupSizes[i] 라고 할때, 각각의 i사람들을 그룹으로 나눠서 리턴하라. 아래 예에서 i=0 인 사람의 그룹크기는 3이어야함.

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/

해결

해시테이블 두개 사용.

#define HSIZE 501

struct elem {
    int person;
    struct elem *next;
};
struct elem *per_table[HSIZE];

struct elem *hash_add(int person, int gsize)
{
    struct elem *node = malloc(sizeof(struct elem));
    node->person = person;
    node->next = per_table[gsize];
    per_table[gsize] = node;
    return node;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** groupThePeople(int* groupSizes, int groupSizesSize, int* returnSize, int** returnColumnSizes){
    int table[HSIZE] = {0,}; // table[group size] = how many people on the group size
    int nr_group = 0;
    int gidx = 0;
    
    for (int i = 0; i < groupSizesSize; i++) {
        table[groupSizes[i]]++;
        hash_add(i, groupSizes[i]);
    }
    for (int gsize = 0; gsize < HSIZE; gsize++) {
        if (!table[gsize])
            continue;
        for (int j = 0; j < table[gsize] / gsize; j++)
            nr_group++;
    }
    *returnSize = nr_group;
    int **ret = (int **)malloc(nr_group * sizeof(int *));
    *returnColumnSizes = (int*)malloc(sizeof(int)*nr_group);
    for (int gsize = 0; gsize < HSIZE; gsize++) {
        if (!table[gsize])
            continue;
        for (int j = 0; j < table[gsize] / gsize; j++) {
            (*returnColumnSizes)[gidx] = gsize;
            ret[gidx] = (int *)malloc(table[gsize] * sizeof(int));
            struct elem *node = per_table[gsize];
            for (int k = 0; k < gsize; k++) {
                ret[gidx][k] = node->person;
                node = node->next;
            }
            gidx++;
        }
    }
    return ret;
}