[프로그래머스] H-Index

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

문제에 따르면 논문 $n$편 중, $h$번 이상 인용된 논문이 $h$편 이상이고, 나머지 논문이 $h$번 이하 인용되었다면 $h$의 최댓값을 H-Index라고 한다.

예를들어 인용수가 [3, 0, 6, 1, 5]라고 하면, H-index는 3이 된다.

H-Index를 구하기 위해 정렬을 먼저 하면 [0, 1, 3, 5, 6]가 되는데 3까지는 $h$번 이상 인용된 논문의 수가 $h$이상이고 5부터는 $h$번 이상 인용된 논문의 수가 $h$보다 작게된다.

이렇게 $h$번 이상 인용된 논문의 수가 $h$보다 작게되는 원소를 찾으면 최종 H-Index의 범위는 (이전 원소 값) ~ (현재 원소 값)사이에 위치하게 된다. 따라서 (현재 원소 값)부터 (이전 원소 값)에 대하여 for문을 돌고, $h$번 이상 인용된 논문의 수가 $h이상이 되는 값이 나오면 그 값이 바로 H-Index가 된다.

def solution(citations):
    # len(citations) : 1 <= n <= 1000
    answer = 0
    
    citations.sort() # O(nlogn)
    
    max_h = -1
    for i in range(len(citations)):
        h = citations[i]
        n_h_over = len(citations) - i
        
        if n_h_over >= h:
            max_h = h
        else:
            for h in range(citations[i], max_h-1, -1):
                if n_h_over >= h:
                    max_h = h
                    
                    return max_h
    
    return max_h