[LeetCode] 275. H-Index II

출처: https://leetcode.com/problems/h-index-ii/

H-Index II - LeetCode

문제

citations[i]가 한 연구자의 i번째 논문의 인용수를 나타내는 정수인 배열 citations가 주어지고, citations는 오름차순으로 정렬되어 있을 때, 그 연구자의 h-index를 반환하라.

 

위키피디아 정의에 따르면, h-index란 한 과학자가 쓴 n개의 논문 중 최소 h의 인용수를 갖는 논문이 h개있다는 것이고, 나머지 n-h개의 논문은 h미만의 인용수를 갖음을 의미한다.

 

만약 가능한 h값이 여러개 있다면, 가장 큰 하나를 h-index로 선정한다.

 

로그 시간 안에 동작하는 알고리즘을 작성해야 한다.

예제

Input: citations = [0,1,3,5,6]
Output: 3

Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Input: citations = [1,2,100]
Output: 2

풀이

정렬되어 있는 배열 그리고 로그 시간이라는 제약사항을 보고 떠오르는 방법은 Binary Search(이진 탐색)이다.

 

이진 탐색은 정렬되어 있는 탐색 범위에서 매 시도마다 반으로 줄이기 때문에 O(logN)의 탐색시간을 갖는 대표적인 알고리즘입니다.

 

코드를 보면서 구체적인 풀이 방법에 대해서 이야기해보자.

var hIndex = function(citations) {
    let ans = 0;

    const N = citations.length
    let lo = 0, hi = N;
    while (lo <= hi) {
        const mid = lo + Math.trunc((hi - lo)/2);

        if (citations[mid] >= N - mid) {
            ans = Math.max(ans, N - mid);
            hi = mid - 1;
        } else {
            if (citations[mid]) ans = Math.max(ans, citations[mid]);
            lo = mid + 1;
        }
    }
    return ans;
};

이진 탐색의 lo와 hi를 움직이는 조건에 대해서 생각해보자.

 

여러 조건을 만들 수 있겠지만, citations[mid]을 가지고 다음의 두 그룹으로 나누었다.

• citations[mid] > N - mid
• citations[mid] <= N - mid

 

여기서 N-mid는 citations[mid] 이상의 인용수를 갖는 논문의 수를 의미한다.

 

첫 번째 케이스인 citations[mid] > N - mid는 citations[mid]보다 큰 인용수를 갖는 논문의 수가 citations[mid]보다 적은 케이스를 의미한다.

 

이 경우 N - mid이 h-index의 후보가 될 것 이고, N - mid보다 더 큰 h-index 후보가 존재하는지 계속해서 찾아야한다. 그러기 위해서 현재의 N - mid보다 다음 단계에서의 N - mid이 더 넓게 설정되어야 하고, 이를 위해서 hi = mid - 1로 움직여야 한다.

 

두 번째 케이스인 citations[mid] <= N - mid은 인용수 citations[mid]보다 큰 인용수를 갖는 논문이 citations[mid]보다 많음을 의미하고, h-index 후보는 citations[mid]이 된다.

 

이때도 현재 citations[mid]보다 더 큰 citations[mid]이 조건을 만족할 수있기때문에 lo = mid + 1로 옮겨 다음 탐색을 반복적으로 수행한다.

 

Github: 275.js