[코테] 99클럽 코테 스터디 28일차 TIL - 배열

Question1 - [미들러] 사람들을 주어진 사이즈대로 그룹화하기 (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/

 

There are n people that are split into some unknown number of groups. Each person is labeled with a unique ID from 0 to n - 1.

You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in. For example, if groupSizes[1] = 3, then person 1 must be in a group of size 3.

 

Return a list of groups such that each person i is in a group of size groupSizes[i].

 

Each person should appear in exactly one group, and every person must be in a group. If there are multiple answers, return any of them. It is guaranteed that there will be at least one valid solution for the given input.

 

Example 1:

• Input: groupSizes = [3,3,3,3,3,1,3]
• Output: [[5],[0,1,2],[3,4,6]]

 

Explanation: 

• The first group is [5]. The size is 1, and groupSizes[5] = 1.
• The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
• The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
• Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

 

Constraints:

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

---

문제풀이

 

trial1

이 문제는, 0~n-1이라는 숫자를 부여받은 n명의 사람이 주어지고,

groupSize라는 리스트에 각 인덱스별로 해당 사람이 어떤 사이즈에 그룹에 속하는지 정보가 주어졌을 때, 사람들을 그룹화하여 리스트를 반환하는 배열 문제였다.

 

주어진 groupSizes 리스트를 기반으로 각 사람이 속해야 하는 그룹으로 나눌 때 다양한 경우의 수가 있는데, 이 문제에서는 올바른 사이즈들로 모든 사람을 그룹화 했다면 그 어떤 케이스를 반환해도 상관 없었다.

 

따라서, 딕셔너리를 사용하여 각 그룹 크기별로 사람들의 인덱스를 저장하고,

지정된 크기만큼 모일 때마다, 조건을 만족할 시 바로 그룹을 형성하여 결과 리스트에 추가하도록 코드를 짜면 되었음.

 

class Solution(object) : 
	def groupThePeople(self, groupSizes): 
    
    	groupsize_hash = {}
        result = []
        
        # 그룹 사이즈별 인덱스 담는 해시 
        if i, size in enumerage(groupSizes) : 
            if size not in groupsize_hash : 
            	groupsize_hash[size] = []
            groupsize_hash[size].append(i)
            
            if len(groupsize_hash[size]) == size :  # 명수가 다 찰 경우 result에 포함
            	result.append(groupsize_hash[size])
                groupsize_hash[size] = []
                
		return result