Leetcode 2910. Minimum Number of Groups to Create a Valid Assignment

문제 링크

 - 그룹의 수를 최소화 해야하기 때문에 그룹안에 ball을 최대한 많이 넣어야 한다 (그리디)

 - 그룹핑을 할 때 나머지가 있으면 나머지로 그룹을 만들 수 있는지 확인해야 한다. 

function minGroupsForValidAssignment(balls: number[]): number {
  const map = new Map<number, number>();
  for (const n of balls) {
    map.set(n, (map.get(n) || 0) + 1);
  }

  let min = balls.length;
  for (const v of map.values()) {
    min = Math.min(min, v);
  }

  // size는 min 값부터 시작 (가장 큰 그룹을 만들 수 있는 크기, 그리디) 
  for (let size = min; size >= 1; --size) {
    const numGroups = groupify(map, size);
    if (numGroups > 0) return numGroups;
  }

  return balls.length;
}

function groupify(map: Map<number, number>, size: number): number {
  let groups = 0;
  const next = size + 1;

  for (const value of map.values()) {
    const numGroups = Math.floor(value / next);
    const remaining = value % next;

    if (remaining === 0) {
      groups += numGroups;
    } else if (numGroups >= size - remaining) {
      // 그룹 하나 더 만들 수 있는지 확인
      // 더 만들 수 있는지 확인에는 next가 아닌 size를 비교. 
      groups += numGroups + 1;
    } else {
      // size로 쪼개질 수 없는 그룹
      return 0;
    }
  }

  return groups;
}