한 연구자의 논문 인용 횟수 배열(모두 음이 아닌 정수)이 주어졌을 때, 이 배열은 오름차순(비내림차순)으로 정렬되어 있습니다. 우리는 이 연구자의 H-인덱스(h-index)를 계산하는 함수를 작성해야 합니다.
H-인덱스의 정의는 다음과 같습니다. "어떤 과학자가 총 N편의 논문 중 h편의 논문이 각각 최소 h번 이상 인용되었고, 나머지 N − h편의 논문은 각각 h번 이하로 인용되었다면, 그 과학자의 인덱스는 h입니다."
예를 들어 입력이 citations = [0, 1, 4, 5, 6]이라면 출력은 3이 됩니다. 연구자가 5편의 논문을 발표했으며, 각 논문은 각각 0, 1, 4, 5, 6번 인용되었습니다. 이 중 3편의 논문이 최소 4번 이상 인용되었고, 나머지 2편은 4번 이하로 인용되었으므로 H-인덱스는 3입니다.
알고리즘 접근 방법
배열이 이미 정렬되어 있기 때문에 선형 탐색 대신 이진 탐색(Binary Search)을 활용하면 O(log n) 시간 복잡도로 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 인덱스 mid 위치에서, mid보다 뒤에 있는 논문의 개수는 n − mid개입니다. 만약 A[mid]가 n − mid보다 크거나 같다면, 적어도 n − mid편의 논문이 각각 A[mid]번 이상 인용된 것이므로 더 왼쪽을 탐색해 답을 좁혀갑니다.
ans := 0, low := 0, n := 배열의 크기, high := n − 1 로 초기화합니다.
배열의 크기가 0이면 0을 반환합니다.
low <= high 동안 반복합니다.
mid := low + (high − low) / 2 를 계산합니다.
A[mid] == n − mid 라면 조건을 정확히 만족하므로 A[mid]를 반환합니다.
A[mid] > n − mid 라면 high := mid − 1 로 왼쪽 범위를 탐색합니다.
그렇지 않으면 low := mid + 1 로 오른쪽 범위를 탐색합니다.
반복이 끝나면 n − high − 1 을 반환합니다.
C++ 예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int hIndex(vector<int>& A) {
int ans = 0;
int low = 0;
int n = A.size();
int high = n - 1;
if(A.size() == 0) return 0;
while(low <= high){
int mid = low + (high - low) / 2;
if(A[mid] == A.size() - mid){
return A[mid];
}
else if(A[mid] > (n - mid)){
high = mid - 1;
}
else low = mid + 1;
}
return n - (high + 1);
}
};
main(){
Solution ob;
vector<int> v = {0,1,4,5,7};
cout << (ob.hIndex(v));
}
입력
[0,1,4,5,6]
출력
3