연구자의 논문별 인용 횟수가 담긴 배열이 주어졌을 때, 해당 연구자의 H-지수(H-index)를 계산하는 함수를 만들어 보겠습니다.
H-지수란 무엇인가?
H-지수는 연구자의 논문이 학계에 미치는 영향력을 평가하는 대표적인 지표입니다. 공식적인 정의는 다음과 같습니다.
"연구자의 전체 논문 수가 N일 때, 그중 h편의 논문이 각각 최소 h번 이상 인용되었고, 나머지 N − h편의 논문은 각각 h번 이하로 인용되었다면, 이 연구자의 H-지수는 h이다."
예를 들어 인용 배열이 [5, 4, 1, 2, 6]이라면 결과값은 3이 됩니다. 3회 이상 인용된 논문이 정확히 3편(4, 5, 6) 존재하기 때문입니다.
해결 알고리즘
이 문제는 버킷(Bucket) 정렬 아이디어를 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 절차는 다음과 같습니다.
- 배열의 크기를 n으로 설정하고, 크기가 n + 1인 버킷(bucket) 배열을 생성합니다.
- i를 0부터 n − 1까지 순회하며 다음을 수행합니다.
- x := c[i]
- 만약 x ≥ n이라면 bucket[n]을 1 증가시키고, 그렇지 않으면 bucket[x]를 1 증가시킵니다. (n 이상의 인용 수는 모두 한곳에 누적)
- 카운터 cnt := 0으로 초기화합니다.
- i를 n부터 0까지 역순으로 순회합니다.
- cnt에 bucket[i] 값을 누적합니다.
- cnt ≥ i를 만족하는 순간 i를 반환합니다. 이것이 바로 H-지수입니다.
- 조건을 만족하지 못하면 −1을 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(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 = {5, 4, 1, 2, 6};
cout << (ob.solve(v));
}
입력
[5, 4, 1, 2, 6]
출력
3
복잡도 분석
이 알고리즘은 배열을 두 번만 순회하므로 시간 복잡도는 O(n), 버킷 배열 저장을 위해 공간 복잡도 역시 O(n)입니다. 정렬(O(n log n))을 사용하는 방식보다 더 효율적이라는 점이 핵심 장점입니다.