leetcode 1282, Group the People Given the Group Size They Belong To

문제 설명

 

n 명의 사람들이 주어지고 ID가 0부터 n-1까지 부여된다고 하자. 이때 groupSizes에는 i 번째 사람이 들어가야 할 그룹의 사람 수가 정의 되어 있다. 즉, groupSizes[i]의 의미는 i 번째 사람이 groupSizes[i] 사이즈의 그룹이 들어가야 한다는 의미이다. 예를 들어 i가 3이고 groupSizes[i]가 2라고 하면 id가 3인 사람은 사이즈가 2인 그룹에 들어가야 한다는 의미이다.

 

이때 가능한 경우를 2차원 리스트로 반환하는데, 여러 가지 정답이 있다면 그 중 하나만 반환하도록 하라.

 

https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/

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

문제 풀이

문제의 조건을 보면 n은 1부터 500까지이다. 시간 초과에 대한 부담이 없으므로 group을 저장할 최대 크기를 500으로 잡고 시작했다.

        List<List<Integer>> answer = new ArrayList<>();
        List<List<Integer>> group = new ArrayList<>();

        for (int i=0; i<=500; i++) {
            group.add(new ArrayList<>());
        }

그리고 group의 i를 그룹의 사이즈로 잡고 각 사이즈 별로 사람의 id를 넣어주었다.

        for (int i= 0; i<groupSizes.length; i++) {
            group.get(groupSizes[i]).add(i);
        }

다음에는 0부터 500까지 돌면서 만일 리스트에 값이 있어서 그룹을 만들어야 한다면, 해당 리스트에 있는 id를 하나씩 돌도록 했다. 일단 해당 리스트에 있는 id 값을 하나씩 tmp에 넣어주다가 만일 index가 i와 같아서 그룹에 사람이 다 찬다면 answer에 넣은 후 tmp와 index를 초기화 했다. 그리고 맨 마지막 그룹은 2차 for문을 나오면 들어가지 않기에 1차 for문으로 들어가기 전 한 번 더 넣어주었다.

        for (int i=0; i<=500; i++) {
            if (group.get(i).size() != 0) {
                //System.out.println(i + " 값이 존재한다.");
                int index = 0;
                List<Integer> tmp = new ArrayList<>();
                for (int j=0; j<group.get(i).size(); j++) {
                    if (index == i) {
                        //System.out.println("새로운 리스트가 필요하다.");
                        index = 0;
                        answer.add(tmp);
                        tmp = new ArrayList<>();
                    }
                    
                    tmp.add(group.get(i).get(j));
                    index++;
                }
                answer.add(tmp);
            }
        }

HashMap을 이용한 풀이

나는 모든 그룹의 사이즈를 가늠하기 힘들어서 최댓값을 넣어줬지만 HashMap을 이용해서 푸는 방법도 있다.

 

일단 groupSizes가 key이고 id 리스트가 value인 map을 만들어 준다. 그리고 groupSizes를 하나씩 돌면서 처음 나온 사이즈면 ArrayList<>를 넣어준다. 그리고 내가 위에서 이차원 리스트를 가지고 했듯이 groupSizes를 기준으로 id인 i를 넣어준다.

 

이때 map의 해당 groupSizes가 현재의 groupSizes와 같다면 answer에 그 map의 value를 넣어주고 clear를 해준다.

        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i=0; i<groupSizes.length; i++) {
            map.putIfAbsent(groupSizes[i], new ArrayList<>());
            map.get(groupSizes[i]).add(i);

            if (map.get(groupSizes[i]).size() == groupSizes[i]) {
                answer.add(new ArrayList<>(map.get(groupSizes[i])));
                map.get(groupSizes[i]).clear();
            }
        }

코드

java

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> answer = new ArrayList<>();
        List<List<Integer>> group = new ArrayList<>();

        for (int i=0; i<=500; i++) {
            group.add(new ArrayList<>());
        }

        for (int i= 0; i<groupSizes.length; i++) {
            group.get(groupSizes[i]).add(i);
        }

        for (int i=0; i<=500; i++) {
            if (group.get(i).size() != 0) {
                //System.out.println(i + " 값이 존재한다.");
                int index = 0;
                List<Integer> tmp = new ArrayList<>();
                for (int j=0; j<group.get(i).size(); j++) {
                    if (index == i) {
                        //System.out.println("새로운 리스트가 필요하다.");
                        index = 0;
                        answer.add(tmp);
                        tmp = new ArrayList<>();
                    }
                    
                    tmp.add(group.get(i).get(j));
                    index++;
                }
                answer.add(tmp);
            }
        }

        return answer;
        
    }
}

import java.util.*;
import java.io.*;

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> answer = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i=0; i<groupSizes.length; i++) {
            map.putIfAbsent(groupSizes[i], new ArrayList<>());
            map.get(groupSizes[i]).add(i);

            if (map.get(groupSizes[i]).size() == groupSizes[i]) {
                answer.add(new ArrayList<>(map.get(groupSizes[i])));
                map.get(groupSizes[i]).clear();
            }
        }
        return answer;
        
    }
}