여러 사람이 서로 친구 요청을 보낸다고 가정해 봅시다. 각 사람의 나이는 ages[i] 배열에 저장되어 있으며, 이 값은 i번째 사람의 나이를 의미합니다. 이때 아래 조건 중 하나라도 참이면, A는 B(B ≠ A)에게 친구 요청을 보내지 않습니다.
age[B] <= 0.5 * age[A] + 7age[B] > age[A]age[B] > 100 && age[A] < 100
세 조건 모두 해당하지 않는 경우에만 A가 B에게 친구 요청을 보냅니다. 단, A가 B에게 요청했다고 해서 B도 반드시 A에게 요청하는 것은 아니며, 자기 자신에게 친구 요청을 보내는 경우는 없습니다. 따라서 우리가 구해야 할 답은 총 몇 건의 친구 요청이 발생하는지입니다.
참고로 세 번째 조건은 사실 두 번째 조건에 이미 포함되어 있습니다. age[B] > 100이고 age[A] < 100이면 당연히 age[B] > age[A]이기 때문입니다. 그럼에도 문제 명세에는 세 조건이 모두 명시되어 있습니다.
예를 들어 나이 배열이 [16, 17, 18]이라면 결과는 2가 됩니다. 실제로 발생하는 요청은 17 → 16, 18 → 17로 총 두 번이기 때문입니다.
해결 접근 방법
나이 값의 범위가 제한적이라는 점을 활용하면 이 문제를 효율적으로 풀 수 있습니다. 카운팅 배열(bucket)과 누적 합(prefix sum)을 사용하는 방법을 단계별로 살펴보겠습니다.
- 크기 1000의
bucket배열을 선언하고, ages 배열에 등장하는 각 나이의 빈도수를 저장합니다. - bucket 배열에 누적 합을 계산해 다시 저장합니다. 이렇게 하면
bucket[x]는 나이가 x 이하인 사람의 수를 의미하게 됩니다. ret을 0으로 초기화합니다.- i를 0부터 ages 배열 크기 - 1까지 반복하며 다음을 수행합니다.
x = ages[i],y = (ages[i] / 2) + 7- x ≥ y인 경우, ret에
bucket[x] - bucket[y]를 더합니다. 이 값은 나이가 y 초과 x 이하인, 즉 A의 요청 대상이 될 수 있는 사람의 수입니다. bucket[x] - bucket[y]가 0이 아니라면 ret에서 1을 빼서 자기 자신을 제외합니다.
- 모든 순회가 끝나면 ret을 반환합니다.
핵심 아이디어는 각 사람마다 다른 모든 사람과 나이 조건을 일일이 비교하는 O(n²) 완전 탐색 대신, 누적 합 배열을 통해 특정 나이 구간에 속하는 사람의 수를 O(1)에 구하는 것입니다.
C++ 구현 예제
#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
복잡도 분석
- 시간 복잡도: O(n + M) — n은 사람의 수, M은 고려하는 최대 나이(1000)입니다. 빈도수 계산에 O(n), 누적 합 계산에 O(M), 마지막 순회에 O(n)이 소요됩니다.
- 공간 복잡도: O(M) — 크기 1000의 bucket 배열 하나만 추가로 사용합니다.