[Leetcode]1282. Group the People Given the Group Size They Belong To

문제 요약

• 알고리즘 분류: Hash, list
• 난이도: Medium
• 문제내용:
  • groupSizes라는 정수 배열이 주어지는데, 여기서 groupSizes[i]는 사람 i가 속한 그룹의 크기이다.
  • 그룹은 groupSize 크기 만큼 그룹에 속해야 한다.
  • 각 사람이 groupSizes[i]의 크기를 가진 그룹에 속하는 그룹의 목록을 반환해라
• 사이트 주소: https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/

문제풀이 

 이번 문제는 Hash와 리스트를 활용 하면되는 간단한 문제 이다. 구현은 아래와 같이 하면된다.

1. 결과에 담을 2차원 리스트와 Hash에 저장할 변수를 선언한다. Hash의 key-value는 groupSize- 인덱스 담을 리스트로 구성한다.
2. groupSize 크기 만큼 반복문을 돌린다.
3. i번째에서 Hash key값이 없을 경우 추가하고 그 key값 리스트에 추가한다.
4. 추가한후 key값의 리스트 크기와 i번째 size와 같을때 결과 리스트에 추가하고 key의 리스트는 초기화 한다.

 위와 같이 구현은 하면 시간 복잡도는 O(N^2)만큼 나올것이다. Hash활용만 하면 문제는 쉽게 풀수 있을 것이다.

Code

Python

• defaultdict은 일반 dictionaly다르게 초기값을 지정하면 없을때 지정값 초기값으로 반환 한다. 그러면 없을경우 NullExeption 오류가 안난다.
• deepCopy는 그냥 저장하고 초기화면 result에 안에 있는 값 같이 초기화 하기 때문에 이와 같은 현상을 방지 하기 위해서 deepcopy를 사용한다.

from collections import defaultdict
from copy import deepcopy

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        result = [] # 결과에 담을 변수
        length = len(groupSizes)
        map = defaultdict(list)

        for i in range(length):
            size = groupSizes[i]
            # map에 키값이 없을 경우 새로 추가 한다.
            if size not in map.keys():
                map[size] = []

            map[size].append(i)
            
            # map value와 size와 같을 경우 결과 리스트에 추가하고 value 리스트를 초기화 한다.
            if len(map[size]) == size:
                result.append(deepcopy(map[size]))
                map[size].clear()

        return result

Java

1. result.add(new ArrayList<>(map.get(size))): 그냥 리스트를 저장하지 않고 new로 선언해서 저장한 이유는 Java의 Call By 개념 때문이다. 그냥 저장 할 경우 같은 주소 값을 가진 리스트를 저장 한다. 그러면 clear 사용 할 경우 결과에 저장한 리스트도 같이 초기화 한다. 이 와 같은 현상을 방지 하기 위해서 새 인스트턴스에 담아서 저장하면 clear 해도 영향을 가지 않는다.

import java.util.*;

class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> result = new ArrayList<>(); // 결과
        int length  = groupSizes.length;
        Map<Integer, List<Integer>> map = new HashMap<>(); // map

        int size;
        for(int i = 0; i < length; i++){
            size = groupSizes[i];
            // Map에 없을 경우 리스트 추가
            if(!map.containsKey(size)){
                map.put(size, new ArrayList<>());
            }

            map.get(size).add(i);

            // Group Size와 리스트 길이 같을때 Result에 저장
            if(map.get(size).size() == size){
                result.add(new ArrayList<>(map.get(size)));
                map.get(size).clear();
            }
        }

        return result;
    }
}