[LeetCode] 275. H-Index 2

문제링크

각 배열의 원소가 인용된 횟수를 나타내는 배열이 오름차순으로 주어졌을 때, h개의 논문이 최소 h번의 인용이 된, h의 최댓값을 구하는 문제이다.

예를 들어 배열이 [0, 1, 3, 5, 6]으로 주어졌을 때, h가 3이라면, 3개의 논문이 최소 3번 인용이 되는 조건을 만족한다.

O(N)으로 풀기

아래와 같이 배열이 있다고 할때,

i	0	1	2	3	4
citations	0	1	3	5	6

i=0일 때, 최대 citation이 0이므로 h-index가 5(배열 길이 - i)가 될 수 없다.
i=1일 때, 최대 citation이 1이므로 h-index가 4가 될 수 없다.
i=2일 때, 최대 citation이 3이므로 h-index는 3(=5-2)이 될 수 있다.

따라서 정리하면, 배열을 0번째부터 순회하다가, i번째 citation이 배열 길이에서 i를 뺀 값보다 크거나 같으면 h-index의 최댓값이 되는 것이다.

이걸 코드로 정리하면

int hIndex(int* citations, int citationsSize){

    for(int i=0;i<citationsSize;i++)
    {
        if(citations[i]>=citationsSize-i) return citationsSize-i;
    }

    return 0;
}

O(logN)으로 풀기

binary search를 이용하면 O(logN)으로 풀 수 있다.

배열의 가운데를 선택했을 때, 그 citation 값이 배열의 전체 길이에서 가운데 인덱스를 뺀 값보다 크거나 같으면, 가운데 인덱스를 변수에 저장해두고, 가운데를 기준으로 앞쪽의 배열에 대해 동일한 작업을 수행한다.
만약 반대의 경우라면, 가운데를 기준으로 뒤쪽의 배열에 대해 동일한 작업을 수행한다.

이걸 코드로 정리하면

int binary_search(int* citations, int l, int r, int n) {
    int answer = 0;

    while(l<=r) {
        int mid = l+(r-l)/2;

        if(citations[mid]>=n-mid) {
            answer = n-mid;
            r=mid-1;
        }
        else l=mid+1;
    }

    return answer;
}
int hIndex(int* citations, int citationsSize){
    return binary_search(citations, 0, citationsSize-1, citationsSize);
}