[LeetCode] 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/

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.

제한 사항
1. groupSizes.length == n
2. 1 <= n <= 500
3. 1 <= groupSizes[i] <= n

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

이 문제에서 주어진 groupSizes 배열은 각 인덱스가 unique ID로 해당 인덱스에 따라 가능한 그룹의 사이즈들이 저장되어 있습니다.
Greedy 한 단순 탐색 문제이지만 배열 원소를 다루는 숙련된 능력을 요구하는 문제였습니다. 다음은 문제 해결 과정입니다.

1. set 객체를 이용하여 중복을 제거해 해당 배열에 저장된 그룹 사이즈 종류를 구해줍니다.
2. 1번에서 구한 그룹 사이즈 종류를 순회합니다.
3. 주어진 배열의 인덱스를 순회하면서 해당 인덱스의 값과 그룹 사이즈 종류를 비교해 같을 경우 해당 값을 새로 저장합니다.
4. 위 반복문에서 구한 새로운 배열을 반환할 리스트에 저장해줍니다.
5. 만약 위 반복문에서 구한 새로운 배열의 길이가 그룹 사이즈보다 크다면 그룹 사이즈에 맞게 리밸런싱해줍니다.

 

위 방법처럼 set으로 그룹 사이즈를 따로 저장할 수도 있고, defaultdict 를 이용하여 그룹 크기별로 구분해 저장할 수도 있습니다.
key와 value 값을 순회하고 for 반복문을 size에 맞게 순회하도록 하여 그룹핑하게 됩니다.

 

딕셔너리를 활용할 때 가독성이 조금 더 좋고 값의 활용이 효율적인 것을 확인할 수 있습니다.

  

💡 내가 해결한 방식은?

set을 이용한 방식

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        # 같은 그룹 크기끼지 분류?
        # 인덱스 값을 저장하므로 이 부분 유의
        sizeList = set()
        for groupSize in groupSizes:
            sizeList.add(groupSize)
            
        sizeList = list(sizeList)
        result = []
        
        for sizeIdx in sizeList:
            tempList, splitList = [], []
            for i in range(len(groupSizes)):
                if groupSizes[i] == sizeIdx:
                    tempList.append(i)
                
            # 리스트 크기가 해당 사이즈보다 클 경우 리밸런싱
            if len(tempList) > sizeIdx:
                for i in range(1, len(tempList)+1):
                    splitList.append(tempList[i-1])
                    if i % sizeIdx == 0:
                        result.append(splitList)
                        splitList = []
                continue
            
            result.append(tempList)
        
        return result

defaultdict를 이용한 방식

from collections import defaultdict

def groupThePeople(groupSizes):    
    # Step 1: 그룹 크기별로 사람들을 모음
    size_to_people = defaultdict(list)
    for person, size in enumerate(groupSizes):
        size_to_people[size].append(person)
    
    result = []
    
    # Step 2: 각 그룹 크기에 해당하는 사람들을 그룹으로 나눔
    for size, people in size_to_people.items():
        for i in range(0, len(people), size):
            group = people[i:i + size]
            result.append(group)
    
    return result

 

---

✍️  TIL

딕셔너리 활용을 시도했지만 생각보다 구현에 어려움을 느껴 빠르게 set을 활용한 풀이로 진행해보았다.
문제를 풀기 전에 주석으로 풀이 과정을 정리한 후 코드 작성을 진행하는 습관을 길러야겠다.
물론 문제가 쉽다면 빠르게 작성해도 되지만 한번씩 막히는 순간이 찾아온다면 지름길을 찾지말고 차분하게
주석으로 문제 흐름을 정리한 후 코드를 작성해나가는게 가장 효율적인 방법이라고 생각했다.
다양한 방식으로 풀어낼 수 있는 문제인만큼 정답보다 내 문제 해결력에 초점을 두고 리뷰해보았다.