[Leetcode] 274. H-Index - JS

https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 정수 배열 citations
- citations[i]는 i번째의 논문이 인용된 횟수를 의미
- h-index는 h번 이상 인용된 h갯수의 논문을 의미

제한조건
--------------------
- n == citation.length
- 1 <= n <= 5000
- 0 <= citations[i] <= 1000

 

2. 접근 방법

접근방법
--------------------
citations 배열을 오름차순 정렬한다.

오름차순 정렬을 함으로써 첫번째 인덱스부터 순회 시
현재 논문을 기준으로 이후에 등장한 논문들은 인용횟수가 현재 논문 보다는 많다는 가정이 성립한다.

그럼 h번 만큼 인용된 논문이 h 갯수 이상인지 구하기 위해선 어떻게 해야할까?

(현재 논문의 인용된 횟수 >= 남은 논문의 갯수)

위 조건이 성립할 때, 최대의 h-index를 구할 수 있다.

 

 

3. 코드

var hIndex = function(citations) {
    let n = citations.length;

    citations.sort((a, b) => a - b);

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

    return 0;
};

 

(현재 논문의 인용된 횟수 >= 현재 논문 포함 남은 논문의 갯수) 조건을 만족할 때의 남은 논문의 갯수가 h-index 이다.

 

이를 증명하는 방법은 우선 현재 논문의 이후의 논문들은 모두 h번 이상 인용되었다는 것은 오름차순으로 증명되었다.

 

추가로 h번 이상 인용된 논문의 최대 갯수를 구하기 위해서 현재 인용된 논문 이후의 남은 논문 갯수를 통해 알 수 있다.

 

때문에, 이후 논문 인용 횟수는 확인할 필요가 없이 해당 조건을 만족하는 즉시 n - i를 반환한다.

 

 

4. 복잡도 분석

- 시간복잡도: O(n * log(n))

- 공간복잡도: O(1)

 

수학적 논리를 바탕으로 생각을 잘 정리하면 쉽게 풀 수 있지만, 이해하는데 어려움이 있었던 문제였다.