[LeetCode] 781. Rabbits in Forest

문제 출처: https://leetcode.com/problems/rabbits-in-forest/

Rabbits in Forest - LeetCode

문제

토끼의 수가 알려지지 않은 숲이 있다. n 마리의 토끼에게 "너와 동일한 색을 가진 토끼가 얼마나 있니?"라는 질문을 했고, 그 답변을 수집하여 배열 answers에 저장했다. answer[i]는 ith 토끼가 답한 결과이다.

 

배열 answers가 주어질 때, 숲에 살고 있는 토끼의 최소 수 를 반환하라.

예제

Input: answers = [1,1,2]
Output: 5

Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit that answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10,10,10]
Output: 11

풀이

ansewrs[i] = k라고 할때, 그 의미를 생각해보자.

 

ansewrs[i] = k라는 것은 i번째 토끼가 보았을 때, 자신과 같은 색을 갖는 토끼가 k마리 있다는 것이다. 즉, 숲 속에 k+1마리의 토끼가 서로 동일한 색상이다는 것이고, 이를 반대로 생각해보면 k라고 답한 k+1마리의 토끼는 같은 색이라 가정할 수 있다.

 

이 사실을 기반으로 문제 풀이에 필요한 정보를 생각해보자.

1. answers에 대한 빈도
2. 각 빈도에 따른 처리 방안 (k+1보다 작다면? k+1보다 크다면?)

 

먼저 answers의 값의 빈도에 대해 생각해보면, Map 자료구조를 이용하여 구할 수 있다.

var numRabbits = function(answers) {
    const answerCount = new Map();
    for (let answer of answers) {
        if (!answerCount.has(answer)) {
            answerCount.set(answer, 0);
        }
        answerCount.set(answer, answerCount.get(answer) + 1);
    }
}

다음으로 각 빈도에 따른 처리 방안에 대해 생각해보자.

 

우선, 설명하기 쉽게 토끼의 답을 answer, 동일한 답을 한 토끼의 수를 freq라고 할 때, freq를 answer+1씩 나누어가며 같은 색상으로 생각될 수 있는 토끼의 그룹이 몇 개 존재하는지 알아낼 수 있다.

var numRabbits = function(answers) {
    const answerCount = new Map();
    for (let answer of answers) {
        if (!answerCount.has(answer)) {
            answerCount.set(answer, 0);
        }
        answerCount.set(answer, answerCount.get(answer) + 1);
    }

    let ans = 0;

    for (let [answer, freq] of answerCount.entries()) {
        const q = Math.trunc(freq / (answer+1));
        const r = freq % (answer+1);

        ans += q * (answer+1);
        ans += (r == 0) ? 0 : (answer+1);
    }

    return ans;
}

Github: 781.js

opwe37/Algorithm-Study