어떤 연구자가 일정 기간 동안 발표한 논문들의 피인용 횟수를 나타내는 양의 정수 배열이 있다고 가정해 보겠습니다. 우리는 이 배열을 입력으로 받아, 배열에 담긴 인용 데이터를 바탕으로 해당 연구자의 h-지수(h-index)를 구하는 JavaScript 함수를 작성해야 합니다.
h-지수란?
한 연구자가 경력 전체에서 N개의 논문을 발표했다고 할 때, 그중 h개의 논문이 각각 최소 h번 이상 인용되었고, 나머지 N − h개의 논문은 각각 h번 이하로 인용되었다면 이 연구자의 h-지수는 h입니다.
예를 들어 인용 배열이 다음과 같다고 해보겠습니다.
const arr = [1, 6, 3, 0, 5];
이 데이터는 연구자가 총 5편의 논문을 발표했으며, 각 논문이 각각 1회, 6회, 3회, 0회, 5회 인용되었음을 의미합니다.
이 중 3편의 논문은 각각 최소 3번 이상 인용되었고, 나머지 2편은 3번 이하로 인용되었으므로 h-지수는 3이 됩니다.
따라서 이 배열에 대한 출력 결과는 다음과 같습니다.
const output = 3;
구현 방법
가장 효율적인 접근 방식은 카운팅(counting) 기법을 활용하는 것입니다. 논문 수(len)보다 많이 인용된 논문은 모두 len 위치에 몰아 넣고, 각 인용 횟수별 개수를 센 뒤 뒤에서부터 누적합을 계산하면 조건을 만족하는 최댓값 k를 찾을 수 있습니다. 이 방법은 정렬 없이도 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
예제 코드
다음은 위 로직을 구현한 코드입니다.
const arr = [1, 6, 3, 0, 5];
const findHIndex = (arr = []) => {
let possible = [];
let { length: len } = arr;
if (len === 0){
return 0;
};
possible.length = len + 2;
possible = possible.join('-').split('').map(() => 0);
for (let i = 0; i < len; i ++) {
let val = arr[i];
let ind = val > len ? len : val;
possible[ind] += 1;
}
let result = 0;
for (let k = len; k >= 0; k --) {
result += possible[k];
if (result >= k) {
return k;
}
}
};
console.log(findHIndex(arr));
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
3
코드 동작 원리 정리
- 배열 초기화: 논문 수 + 2 크기의 카운트 배열을 만들어 각 인용 횟수의 빈도를 저장합니다.
- 인용 횟수 카운팅: 특정 논문의 인용 횟수가 전체 논문 수(len)보다 크면 len 위치에 카운트합니다. h-지수는 최대 len까지만 가능하기 때문입니다.
- 역방향 누적 합계: 뒤에서부터(k = len → 0) 누적 인용 논문 수를 더하다가, 누적값이 k 이상이 되는 순간의 k가 곧 h-지수입니다.
- 빈 배열 처리: 논문이 하나도 없으면 h-지수는 0입니다.