[C] LeetCode 275. H-Index II

문제

번역

주어진 정수 배열 citations이 있다.

citations의 i번째 원소는 한 연구자가 발표한 i번째 논문이 받은 인용 횟수를 의미한다.

또한 citations 배열은 non-decreasing(감소하지 않는, 즉 오름차순) 순서로 정렬되어 있다.

이때 연구자의 h-index를 반환해라.

 

h-index란 연구자가 발표한 논문 중 적어도 h편의 논문이 각각 h회 이상 인용되었을때, h의 가장 큰 값이다.

접근 방법과 소스코드

이 문제를 풀려고 보니 정렬이 되어 있고, 로그 시간복잡도로 풀라고 되어있었다.

 

일단 citations 배열의 i번째 원소가 h-index 후보가 되려면 

citations[i] >= citationsSize - i 여야 한다.

이는 현재 논문부터 끝까지의 논문이 각각 최소 citationsSize - i번 이상 인용되었다는 뜻이다.

 

그럼 우리는 이를 첫번째로 만족하는 위치를 찾으면 된다.

배열이 정렬되어 있기에 citations[i]는 오른쪽으로 갈수록 커지고

citationsSize - i (논문 개수)는 오른쪽으로 갈수록 점점 작아질 것이다.

 

그러면 citations[i] >= citationsSize - i 는 어느 시점부터는 계속 true가 될 것이다.

그래서 이 지점을 binary search로 찾아내면 된다.

 

int hIndex(int* citations, int citationsSize) {
    int l=0,r=citationsSize-1;
    int rax = 0;

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

        if (citations[m] >= citationsSize - m) {
            rax = citationsSize - m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    return rax;
}

 

계속해서 탐색범위를 줄여나가니 시간 복잡도는 \( O(\log {n})\) 이 될 것이다.

추가적인 사용한 변수는 입력값에 따라 그 개수가 늘어나지 않으니 공간복잡도는 \(O(1)\) 이 될 것이다.