n명의 사람이 있고, 각 사람의 ID는 0부터 n-1까지의 범위에 있다고 가정해 보겠습니다. 모든 사람은 정확히 하나의 그룹에만 속합니다. 길이가 n인 배열 groupSizes가 주어지며, 이 배열은 각 사람이 속한 그룹의 크기를 나타냅니다. 우리의 목표는 실제 그룹들을 찾아내고, 각 그룹에 포함된 사람들의 ID를 구하는 것입니다.
예를 들어 입력이 [3,3,3,3,3,1,3]이라면 출력은 [[5], [0, 1, 2], [3, 4, 6]]이 됩니다. 물론 [[2,1,6],[5],[0,4,3]] 또는 [[5],[0,6,2],[4,3,1]]처럼 그룹 내 순서가 다른 다른 정답도 가능합니다.
문제 해결 접근 방법
이 문제는 맵(std::map 또는 unordered_map)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '같은 그룹 크기를 가진 사람들의 ID를 먼저 모으고, 그 크기만큼씩 잘라내어 그룹을 완성하는 것'입니다. 구체적인 단계는 다음과 같습니다.
- 그룹 크기를 키로, 사람 ID 목록을 값으로 저장할 맵 m을 생성합니다.
- 배열 g를 처음부터 끝까지 순회하면서 인덱스 i를 m[g[i]]에 삽입합니다. 이렇게 하면 동일한 그룹 크기를 가진 사람들의 ID가 한곳에 모입니다.
- 최종 결과를 담을 2차원 벡터 res를 생성합니다.
- 맵의 각 요소(키: 그룹 크기, 값: ID 목록)에 대해 다음을 반복합니다.
- 목록의 원소를 순서대로 임시 벡터 temp에 추가합니다.
- temp의 크기가 해당 키(그룹 크기)와 같아지면 temp 전체를 res에 새 행으로 삽입하고, temp를 비워 다음 그룹을 준비합니다.
- 모든 처리가 끝나면 res를 반환합니다.
맵을 사용하는 경우 시간 복잡도는 O(n log n)이며, unordered_map을 사용하면 평균 O(n)으로 개선할 수 있습니다. 공간 복잡도는 O(n)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<vector<int>> groupThePeople(vector<int>& g) {
map <int, vector <int> > m;
for(int i = 0; i < g.size(); i++){
m[g[i]].push_back(i);
}
vector < vector <int> > res;
map <int, vector <int> > :: iterator i = m.begin();
vector <int> temp;
while(i != m.end()){
for(int j = 0; j < i->second.size(); j++){
temp.push_back(i->second[j]);
if(temp.size() == i->first){
res.push_back(temp);
temp.clear();
}
}
i++;
}
return res;
}
};
main(){
vector<int> v = {3,3,3,3,3,1,3};
Solution ob;
print_vector(ob.groupThePeople(v));
}입력
[3,3,3,3,3,1,3]
출력
[[5],[0, 1, 2],[3, 4, 6]]