[LeetCode] 781. Rabbits in Forest

📌 문제 핵심 요약

• 상황: 토끼들에게 "나랑 같은 색 토끼가 몇 마리 더 있는가?"를 물어본 답변 배열 answers가 주어짐.
• 목표: 숲속에 존재할 수 있는 최소 토끼 수 구하기.

💡 풀이 아이디어

1. 답변 $k$의 의미
   • 답변이 $k$라는 것은 자신을 포함해 해당 색상 그룹의 정원이 $k + 1$마리라는 뜻.
2. 그리디(Greedy) 접근
   • 최소 토끼 수를 만들어야 하므로, 같은 숫자 $k$를 대답한 토끼끼리 최대한 같은 그룹으로 묶어 주는 것이 유리함.
3. 그룹 정원 초과 시
   • 답변 $k$의 등장 횟수가 정원($k + 1$)을 넘어가면, 정원이 가득 찼으므로 새로운 색상의 그룹을 생성해야 함.

📐 핵심 계산식

답변 $k$의 등장 횟수를 freq라고 할 때:

• 그룹당 정원 (groupSize): $k + 1$
• 필요한 그룹 수 (groupCount): $\lceil \text{freq} / \text{groupSize} \rceil$ (Math.ceil 이용)
• 해당 답변의 총 토끼 수: $\text{groupCount} \times \text{groupSize}$

💻 Code (TypeScript)

function numRabbits(answers: number[]): number {
    const groupMap = new Map<number, number>();
    
    // 1. 각 답변별 등장 횟수 카운트
    for (const answer of answers) {
        groupMap.set(answer, (groupMap.get(answer) ?? 0) + 1);
    }
    
    let totalRabbits = 0;
    
    // 2. 답변별 최소 토끼 수 계산 후 합산
    for (const [group, freq] of groupMap) {
        const groupSize = group + 1; // 그룹 정원
        const groupCount = Math.ceil(freq / groupSize); // 필요한 그룹 개수
        
        totalRabbits += groupCount * groupSize;
    }
    
    return totalRabbits;
}