1282. Group the People Given the Group Size They Belong To - medium
문제
There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people’s IDs each group includes.
You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.
제한사항
- groupSizes.length == n
- 1 <= n <= 500
- 1 <= groupSizes[i] <= n
입출력 예
1
2
3
4
5
6
7
8
9
Example 1:
Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation:
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].
Example 2:
Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]
풀이
- Hash, Greedy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
vector<vector<int>> answer;
unordered_map<int, vector<int>> m;
// hash를 이용해 같은 size별 인덱스끼리 나눔
for(auto i = 0 ; i < groupSizes.size() ; ++i){
m[groupSizes[i]].push_back(i);
}
// 사이즈별 인덱스를 해당 사이즈의 vector에 저장
for(auto& sub : m){
vector<int> subVec;
for(auto i = 0 ; i < sub.second.size() ; ++i){
if(subVec.size() == sub.first){
answer.push_back(subVec);
subVec.clear();
subVec.push_back(sub.second[i]);
}
else
subVec.push_back(sub.second[i]);
}
answer.push_back(subVec);
}
return answer;
}
};