이해

• H-Index를 구하는 방법은 다음 아래와 같다.
  • 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 노문이 h편 이상이고 나머지 논문이 h번 이하 인용됐다면 h의 최댓값이 이 과학자의 H-Index이다.
• 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열이 주어질 때, 이 과학자의 H-Index를 return하라.

계획

• citations 배열을 오름차순으로 정렬한다.
• citations 배열에 들어있는 값들 중 maximum 값부터 0까지의 모든 정수마다 h값을 부여한 뒤
• h값으로 적절한 경우에 해당 값을 return해준다.
• 인용 횟수가 h번 이상인 논문의 수는 이분 탐색(optimal binary search)을 이용하여 찾아준다.
• 논문 수: N, 논문 별 인용 횟수: M일 때 시간 복잡도는 O(M * logN)이다.

실행

# 오름차순으로 정렬된 arr 배열에서 x이상인 값의 개수를 반환하는 함수
def count_large(arr, x):
    start = 0
    end = len(arr) - 1
    result = len(arr)
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= x:
            result = min(result, mid)
            end = mid - 1
        else:
            start = mid + 1
    return len(arr) - result
    
def solution(citations):
    citations.sort()

    for h in range(citations[-1], -1, -1):
        if count_large(citations, h) >= h:
            
            return h 

개선

• count_large 함수를 새로 정의하지 않곧 python에서 제공되는 bisect 모듈의 bisect_left 함수를 사용하여 구현한다.

from bisect import bisect_left
    
def solution(citations):
    citations.sort()

    for h in range(citations[-1], -1, -1):
        if len(citations) - bisect_left(citations, h) >= h:
            
            return h 

• 다른 사람의 풀이를 찾아보니 너무 훌륭한 코드를 발견했다..

  def solution(citations):
    citations = sorted(citations)
    l = len(citations)
    for i in range(l):
        if citations[i] >= l-i:
            return l-i
    return 0
  

  • bisect_left 함수를 사용하지 않고 for문을 0부터 시작해서 돌려주었고, h값으로는 논문의 수 이상의 값이 올 수 없기 때문에 citations 배열의 길이만큼만 돌려주었다.
  • 논문 수가 N일 때, 시간복잡도는 O(N * logN)이다.

회고

• 예전에 bisect_left 함수를 사용해본 적이 있었는데 모듈 이름을 잊어버려서 직접 구현해서 풀었다..
• 처음에 for문을 maximum 값부터 minimum값까지 돌려주었는데 테스트 케이스 하나가 틀려서 살짝 헤맸다. citations 배열이 양의 정수 하나만 포함하는 배열인 케이스를 처리하지 못했다. citations 배열이 [5]라면 1을 return해줘야 하기 때문에 maximum 값부터 0까지 돌려주어야 했다. 모든 테스트 케이스를 처리할 수 있도록 잘 생각하고 코드를 짜야겠다.
• 찾아보면 훌륭한 코드들이 많으니까 스스로 구현해 보고 난 뒤에 다른 풀이들을 많이 살펴보고 내 코드를 열심히 개선해봐야겠다.