문제
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.
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]]
Constraints:
groupSizes.length == n 1 <= n <= 500 1 <= groupSizes[i] <= n
풀이
배열이 [2, 1, 3, 3, 3, 2]가 주어졌다고 해보자.
이때 총 6명이 있는데 각각은 id가 0부터 5까지 주어진다. 그리고 배열의 원소가 의미하는건 각 개인이 갖는 그룹의 크기이다.
예를들어 배열[0]에 2가 들어있다. 이것은 id가 0번인 사람은 그룹의 크기가 2인곳에 속한다는 뜻이다.
이럴때 각 그룹이 어떤 아이디들로 구성되는지를 리턴하면 되는 문제이다.
미디움 난이도를 처음으로 풀어 보았다.
이 문제를 보고 아 이거 못풀겠는데.. 하고 조금 고민해보다가 다른 문제 풀어야지.. 라고 생각했는데 생각보단 잘 풀렸던 문제다.
심지어 처음으로 공간복잡도 100$를 받았고 심지어 속도도 85%를 받게 되었다. 너무 기쁘다. 이맛에 알고리즘을 푸는구나 싶었다.
생각의 흐름
배열로 각 그룹의 크기가 주어졌다. [2,1,3,3,3,2]를 예로 들어보자.
여기서 Id가 0번인 사람과 5번인 사람은 같은 그룹에 들어가야한다. 그리고 id가 2,3,4번인 사람도 같은 그룹에 들어가야한다. 보니까 뭔가 같은 그룹 사이즈를 갖는 id끼리 묶어야 쉽게 풀 수 있을것 같은 느낌이 들었다.
이걸 정렬하게 되면 1 2 2 3 3 3 이런식으로 정렬이 되는데 이말은 0번은 혼자 그룹을 짓고 1번과 2번 id를 갖는 둘이서 그룹을 짓고 id 3,4,5번은 3명이서 그룹을 짓게 된다.
근데 중요한건 정렬을 할때 id를 묶어서 같이 해줘야 한다는 것이다.
원 배열을 정렬하는 순간 id가 그룹의 크기와 다르게 매칭된다. 따라서, 아이디와 그룹사이즈를 묶은다음에 그룹사이즈를 기준으로 오름차순 정렬한다. 그럼 다음과 같은 배열 구조를 갖게 할 수 있다.
[[5, 1][0, 3] [1 3][2 3] [3 3][4 3] [6 3]] : [id, groupSize]
이렇게 하게 되면 각 개인의 id를 유지한채로 그룹 사이즈 오름차순으로 정렬할 수 있다.
반복문을 돌면서 그룹의 사이즈가 달라질때마다 하위 반복문을 돌게 했다. 하위 반복문에 들어가기 전에 배열을 하나 선언하고 하위 반복문을 돌면서 그 방금 선언한 배열에 id를 넣어서 id를 그룹화 한다음에
하위 반복문이 종료되면 그 만들어진 하위 배열을 결과 배열에 push하는 구조이다.
/**
* @param {number[]} groupSizes
* @return {number[][]}
*/
var groupThePeople = function(groupSizes) {
const group = [];
for (let i = 0; i < groupSizes.length; i++) {
group.push([i, groupSizes[i]]);
}
group.sort((a, b) => a[1] - b[1]);
const result = [];
for (let i = 0; i < groupSizes.length; i++) {
// [5, 1] [0, 3] [1 3] [2 3] [3 3] [4 3] [6 3] : [id, groupSize]
const ids = [];
for (let j = i; j < i + group[i][1]; j++) {
ids.push(group[j][0]);
}
result.push(ids);
i += group[i][1] - 1;
}
return result;
};결과
