C++의 적절한 나이의 친구

어떤 사람들이 친구 요청을 한다고 가정해 봅시다. 우리는 그들의 나이를 알고 있습니다. 이것은 나이[i]에 저장되어 있습니다. 따라서 이것은 i번째 사람의 나이를 나타냅니다. 이제 다음 조건 중 하나라도 충족되면 A는 B(B !=A)에게 친구 요청을 하지 않습니다. −

• 나이[B] <=0.5 * 나이[A] + 7
• 나이[B]> 나이[A]
• 나이[B]> 100 &&나이[A] <100

그렇지 않으면 A는 B를 친구로 요청할 것입니다. A가 B를 요청하면 B가 반드시 A를 요청하는 것은 아니라고 생각할 수 있습니다. 또한 사람들은 자신을 친구로 요청하지 않을 것입니다. 그래서 우리는 얼마나 많은 총 친구 요청이 이루어졌는지 찾아야 합니까?

연령 배열이 [16,17,18]과 같다면 요청이 17 -> 16, 18 -> 17이 되므로 결과는 2가 됩니다.

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

• 크기 1000의 배열 버킷을 정의한 다음 버킷에 연령 배열 요소의 빈도를 저장합니다.
• 그런 다음 버킷 요소의 누적 합계를 찾아 버킷에 저장합니다.
• ret :=0
• 0에서 연령 배열의 크기 범위에 있는 i의 경우 – 1
  • x :=연령[i], y :=(나이[i] / 2) + 7
  • x>=y이면
    • ret :=버킷[x] – 버킷[y]
    • 버킷[x] – 버킷[y]이 0이 아닌 경우 ret를 1로 줄입니다.
• 반환

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

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numFriendRequests(vector<int>& ages) {
      vector <int> bucket(1000);
      for(int i = 0; i < ages.size(); i++){
         bucket[ages[i]]++;
      }
      for(int i = 1; i < 1000; i++)bucket[i] += bucket[i - 1];
      int ret = 0;
      for(int i = 0; i < ages.size(); i++){
         int x = ages[i];
         int y = ((ages[i]) / 2) + 7;
         if(x >= y){
            ret += (bucket[x] - bucket[y]);
            if((bucket[x] - bucket[y]))
            ret--;
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {16, 17, 18};
   Solution ob;
   cout << (ob.numFriendRequests(v1));
}

입력

[16,17,18]

출력

2