[LeetCode] 781. Rabbits in Forest

https://leetcode.com/problems/rabbits-in-forest/

Rabbits in Forest - LeetCode

Rabbits in Forest - Medium

 

각각의 토끼에게 "너네와 같은 색을 가진 다른 토끼는 몇 마리가 있니?" 라고 물었을때 대답들이 주어진다.

이 대답들을 가지고 유추하여 이곳에 최소한 몇 마리의 토끼가 있어야하는지 묻는 문제다.

 

예시를 보고 유추해보자.

 

-1번 예시

토끼1 : 1마리

토끼2 : 1마리

토끼3 : 2마리

토끼1과 토끼2가 같으면 되고, 토끼3 과 다른 토끼 두마리(토끼4, 토끼5)가 필요하다.

따라서 최소 5마리가 있어야 한다.

 

-2번 예시

토끼1 : 10마리

토끼2 : 10마리

토끼3 : 10마리

토끼1의 대답으로 일단 자신과 같은색의 토끼는 자신 포함해 총 11마리인걸 알 수 있고,

토끼1, 토끼2, 토끼3가 모두 같은 색이어야 한다. 이러면 다른 8마리의토끼(토끼4~토끼11)가 필요하다.

따라서 최소 11마리가 있어야 한다.

 

-추가 예시

2번 예시에서 토끼12마리에게 물어 모두 10마리라고 답했다고 생각해보자.

이 경우, 토끼1~토끼11 까지는 모두 같은 색이라고 하면 토끼1~토끼11은 해결이 된다.

남은건 토끼12 인데, 본인 포함하여 같은색토끼가 토끼1~토끼11과는 다른 또다른 11마리가 되므로,

최소 22마리가 있어야 한다.

 

이를 다시 좀 정리해보자.

토끼의 답과 그 답을 말한 토끼수를 매핑하자.

즉, 2번 예시에서는 {10 : 3}, 추가 예시에서는 {10 : 12} 이 될 것이다.

이 답을 말한 토끼수가 1~11까지는 11마리로 충분하고,

추가 예시에서는 답을 말한 토끼수가 12마리이므로 22마리가 되었다.

이를 잘 계산해보면,

 

(토끼의 답 + 1) * { (답을 말한 토끼 수 - 1)을 (토끼의 답 + 1)으로 나눈 몫 + 1} 로 계산을 할 수 있다.

 

따라서 문제의 풀이는 

hash map을 만들어 토끼의 답과 그 답을 말한 토끼수를 매핑시키고,

위에서 만든 식을 이용해 계산해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        int ret = 0;
        unordered_map<int, int> m;
        for (int a:answers) m[a]++;
        for (auto iter:m) ret += (iter.first+1)*(int)((iter.second-1) / (iter.first + 1) + 1);
        return ret;
    }
};