Intuition

citations.length에 따라 h의 최댓값이 결정되는 점에 주목하여 이진탐색을 진행했다.

Approach

[3,3,100] 이라는 배열이 있을 때, 배열의 길이가 3이므로 h는 최소1, 최소3 의 범위 내에서 구할 수 있다.

1부터 3까지의 범위에서 이진탐색을 진행해보겠다.
중간값은 2이고, 이 값이 정답후보가 되기 위해서는 배열의 뒤에서부터 두번째 부분이 2보다 크거나 같은지만 확인해주면 된다. (배열이 오름차순 정렬이기때문에 그 외에는 확인할 필요가 없다.)

일반화하면, l부터 r까지의 범위에서 이진탐색을 진행한다. (각각, 1과 배열의 크기로 초기화)
중간값이 정답후보가 되려면 배열의 뒤에서부터 mid번째 원소가 mid값보다 크거나 같아야한다.

크거나 같다면, mid는 정답후보가 되고, 조건을 만족하는 더 큰 h가 존재할 수도 있으므로 l은 mid+1이 된다.

그렇지 않다면, mid값이 너무 큰 것이므로 r은 mid-1이 된다.

int hIndex(int* citations, int citationsSize) {
    int ans;
    int l=1;
    int r=citationsSize;

    while (l<=r){
        int mid=l+(r-l)/2;
        if (citations[citationsSize-mid]>=mid){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }

    return ans;
}

그러나 우리가 l을 1로 초기화했기 때문에 배열에 0만 존재하는 경우에 대해서는 대응할 수 없게 된다.

조금 더 구체적으로는 citationsSize가 n이라고 할때, 나올 수 있는 모든 경우의 수는 n+1개이다. 그러나, 우리가 이진탐색으로 살펴보는 범위는 1부터 n까지로, n개이다. 한가지 경우의 수를 빼먹은 것인데 그것이, h가 0이 나오는 경우이다.

따라서 ans를 0으로 초기화하여 이런 케이스까지 대응할 수 있다.

Solution

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

    while (l<=r){
        int mid=l+(r-l)/2;
        if (citations[citationsSize-mid]>=mid){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }

    return ans;
}

Time Complexity

이진탐색의 시간복잡도와 동일하다.
$O(log N)$

지적 및 질문 환영