Intuition 🤔

Sort descendingly. 그러면 현재 배열 인덱스보다 작은 h-index 들은 무조건 h-index가 맞다. 그렇다면 가장 어려운 것은 언제 return을 하는지다.

답안

import java.util.Arrays;

class Solution {
    public int hIndex(int[] citations) {
        int[] sorted = citations; 
        int index = 0;
        
        for (int i = 0; i < citations.length; i++) {
            sorted[i] = -1 * citations[i]; 
        }

        Arrays.sort(sorted); 

        for (int i = 0; i < citations.length; i++) {
            sorted[i] = -1 * citations[i]; 
        } // sorted descending

        for (int i = 0; i < citations.length; i++) {
            if (sorted[i] < i + 1) {
                return i; 
            }
        }

        return 0;
    }
}

설명

먼저 자바에서는 Primitive value를 내림차순으로 정렬하는 API는 없다. Wrapper를 사용해야하는데 그럴바엔 그냥 -1을 두 번 곱하는게 더 마음에 들었다.

시간 복잡도는 O(2n + nlogn) ~ O(nlogn)일 것이다.

Intuition에서의 이유대로 내림차순으로 정렬한 다음 if logic을 보자.

먼저 h-index의 정의는 x번 만큼의 참조 횟수가 있는 논문이 x개 있을때에 그 저자의 h-index는 x이다.

한 저자의 h-index는 내림차순으로 정렬된 citations의 값들 중에 첫번째로 citations[i]의 값이 i보다 작은 숫자이다... 라고 생각했다.
하지만 i는 배열의 인덱스이기 때문에 1을 더해줘야 citations[i]의 값보다 참조 횟수가 같거나 많은 논문의 개수가 나온다.

그러므로 첫번째로 citations[i] < i + 1일때에 citations[i]의 값이 H-index이다.

그리고 만약 그런 h-index가 존재하지 않는다면 그 저자의 h-index는 0이다.