Daily Leetcoding challenge 1282. Group the People Given the Group Size They Belong To

오늘도 찾아온 데일리 챌린지 문제. 배열 & 맵을 사용하는 문제였다.

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/?envType=daily-question&envId=2023-09-11 

Group the People Given the Group Size They Belong To - LeetCode

직관

0부터 n-1까지 ID가 있는 n명의 사람이 있고, i번째 사람은 그룹의 크기가 groupSizes[i]인 그룹에 들어가야 한다. 각 사람은 한 그룹에 한 번만 들어갈 수 있고, 모든 사람이 그룹에 들어가야 한다. 그리고 주어진 input에서 적어도 하나의 유효한 솔루션이 존재한다.

i번째 사람은 그룹 크기가 groupSizes[i]인 그룹에 들어가야 하는데, 덜 채워진 그룹이 있으면 거기에 들어가고, 아니면 새로운 그룹에 들어가면 된다.

접근법

unfilled 맵에 그룹 사이즈만큼 채워지지 못한 그룹을 저장한다.

groupSizes 리스트를 순회하면서 unfilled 맵에 덜 채워진 리스트가 있으면 리스트에 i번째 사람을 추가하고 맵을 업데이트 한다. 만약 리스트의 크기가 groupSize와 같아졌으면, ans에 추가하고, unfilled에서는 삭제한다.

복잡도

시간 복잡도는 O(n), 공간 복잡도는 O(n)이다.

코드

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ans = new ArrayList<>();
        int size = groupSizes.length;
        Map<Integer, List<Integer>> unfilled = new HashMap<>();
        for(int i=0; i<size; i++) {
            int groupSize = groupSizes[i];
            List<Integer> group = unfilled.getOrDefault(groupSize, new ArrayList<>());
            group.add(i);
            if (group.size() == groupSize) {
                ans.add(group);
                unfilled.remove(groupSize);
            } else {
                unfilled.put(groupSize, group);
            }
        }
        return ans;
    }
}