C++의 숲 속의 토끼

<시간/>

숲에서 각 토끼는 어떤 색깔을 가지고 있다고 가정합니다. 이제 토끼의 일부 하위 집합(모두 가능)이 자신과 같은 색을 가진 다른 토끼가 몇 개인지 알려줍니다. 해당 답변은 배열에 배치됩니다. 우리는 숲에 있을 수 있는 최소 토끼 수를 찾아야 합니다. 따라서 입력이 [1,1,2]와 같으면 출력은 5가 됩니다. 둘 다 같은 색일 수 있는 "1"이라고 답한 두 토끼는 흰색이라고 말합니다. 이제 "2"라고 답한 토끼는 흰색이 아니거나 답변이 일관되지 않습니다. "2"라고 답한 토끼가 검은색이라고 가정해 봅시다. 그런 다음 배열에 응답하지 않은 2개의 다른 검은 토끼가 숲에 있어야 합니다. 따라서 숲에서 가능한 가장 작은 토끼 수는 5:3으로 응답한 토끼와 응답하지 않은 2개입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

맵을 m으로 만들고 n :=배열의 크기
ret를 0으로 설정
0 ~ n – 1 범위의 i에 대해
- x :=ans[i]
- x =0이면 ret를 1만큼 증가시키고 이 반복의 다음 부분을 건너뜁니다.
- m에 x가 있으면 ret를 (x + 1) 증가시키고 m[x] :=0으로 설정합니다.
- 그렇지 않으면
  - m[x] 1 증가
  - m[x] =x이면 m에서 x를 삭제합니다.
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numRabbits(vector<int>& ans) {
      map <int, int> m;
      int n = ans.size();
      int ret = 0;
      for(int i = 0; i < n; i++){
         int x = ans[i];
         if(x == 0){
            ret++;
            continue;
         }
         if(!m.count(x)){
            ret += (x + 1);
            m[x] = 0;
            }else{
               m[x]++;
           if(m[x] == x){
               m.erase(x);
            }
         }
      }
      return ret;
   }
};
main(){
   vector<int> v = {1,1,2};
   Solution ob;
   cout << (ob.numRabbits(v));
}

입력

[1,1,2]