Zayden

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

July 25, 2023

문제 설명

n명의 사람들이 알 수 없는 수의 그룹으로 나뉘어 있습니다. 각 사람에게는 0에서 n-1까지의 고유 ID가 부여됩니다.

정수 배열 groupSizes가 주어지며, 여기서 groupSizes[i]는 사람 i가 속해 있는 그룹의 크기입니다. 예를 들어 groupSizes[1] = 3이면 사람 1은 크기가 3인 그룹에 속해야 합니다.

각 사람 i가 groupSizes[i] 크기의 그룹에 속하는 그룹의 목록을 반환합니다.

각 사람은 정확히 하나의 그룹에 나타나야 하며, 모든 사람은 한 그룹에 속해야 합니다. 정답이 여러 개 있으면 그 중 하나를 반환합니다. 주어진 입력에 대해 유효한 해가 하나 이상 있다는 것이 보장됩니다.

  • 예시 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]].
  • 예시2
Input: groupSizes = [2,1,3,3,3,2]
Output: [[1],[0,5],[2,3,4]]

문제 접근

빈 객체를 하나 선언하여 해당 객체의 key를 이용하여 같은 size인 사람들을 저장한다.

  1. size 를 key로 사용하는 빈 객체 하나를 선언한다.
  2. 해당 객체에 size 가 key가 없으면 빈 배열에 index를 추가한다.
  3. 해당 객체에 size 가 key로 존재하면 해당 배열에 index를 추가한다.
  4. 해당 key의 value인 배열이 size 와 동일하면 해당 배열을 result에 추가한다. 그리고 해당 key인 프로퍼티는 제거한다.
  5. 위 과정을 해당 groupSizes 배열에 길이만큼 순회한다. 
function solution(groupSizes) {
    if (groupSizes.length === 1) {
      return [[0]];
    }

    const result = [];
    const info = {};

    for (let i = 0; i < groupSizes.length; i++) {
      const size = groupSizes[i];

      if (info.hasOwnProperty(size)) {
        info[size].push(i);
      } else {
        info[size] = [i];
      }

      if (info[size].length === size) {
        result.push(info[size]);
        delete info[size];
      }
    }

    return result;
}