연구자의 논문 인용 횟수 배열(모두 음이 아닌 정수)이 주어졌을 때, 해당 연구자의 H-지수(H-Index)를 계산하는 함수를 정의하는 문제입니다.
H-지수의 정의는 다음과 같습니다. "어떤 과학자의 N편의 논문 중 h편의 논문이 각각 최소 h번 이상 인용되었고, 나머지 N − h편의 논문은 각각 h번 이하로 인용되었다면, 그 과학자의 지수는 h이다."
예제 이해하기
입력이 citations = [3, 0, 6, 1, 7]이라면 출력은 3입니다. 연구자는 총 5편의 논문을 발표했으며, 각 논문은 3, 0, 6, 1, 7번 인용되었습니다. 최소 3번 이상 인용된 논문이 3편 있고, 나머지 2편은 3번 이하로 인용되었으므로 H-지수는 3이 됩니다.
해결 접근 방법
이 문제는 버킷(bucket) 배열을 활용하면 시간 복잡도 O(n)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 H-지수가 논문 수 n을 넘을 수 없다는 점입니다. 따라서 n보다 큰 인용 횟수는 모두 bucket[n]에 누적하면 됩니다.
- n := 배열의 크기로 설정하고, 크기가 n + 1인 bucket 배열을 생성합니다.
- i를 0부터 n − 1까지 반복합니다.
- x := c[i]
- x ≥ n이면 bucket[n]을 1 증가시키고, 그렇지 않으면 bucket[x]를 1 증가시킵니다.
- cnt := 0으로 초기화합니다.
- i를 n부터 0까지 역순으로 반복합니다.
- cnt에 bucket[i]를 더합니다.
- cnt ≥ i이면 i를 반환합니다.
- 조건을 만족하지 않으면 −1을 반환합니다.
뒤에서부터 누적합을 계산하는 이유는, 인용 횟수가 i 이상인 논문의 개수가 처음으로 i 이상이 되는 순간이 곧 H-지수이기 때문입니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int hIndex(vector<int>& c) {
int n = c.size();
vector <int> bucket(n + 1);
for(int i = 0; i < n; i++){
int x = c[i];
if(x >= n){
bucket[n]++;
} else {
bucket[x]++;
}
}
int cnt = 0;
for(int i = n; i >= 0; i--){
cnt += bucket[i];
if(cnt >= i)return i;
}
return -1;
}
};
main(){
Solution ob;
vector<int> v = {3,0,6,1,7};
cout << (ob.hIndex(v));
}입력
[3,0,6,1,7]
출력
3
복잡도 분석
이 알고리즘은 배열을 두 번만 순회하므로 시간 복잡도는 O(n), 크기 n + 1의 버킷 배열 하나만 사용하므로 공간 복잡도 역시 O(n)입니다. 정렬 기반 접근(O(n log n))보다 효율적이며, 대량의 인용 데이터에서도 빠르게 동작합니다.