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

soopsaram·2022년 5월 10일
0

목록 보기
20/125

## 문제

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]]++;
}
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;
}
기록 & 정리 아카이브 용도 (보다 완성된 글은 http://soopsaram.com/documentudy)