[알고리즘] 프로그래머스 - H-index

June·2021년 3월 3일
0

알고리즘

목록 보기
111/260

프로그래머스 - H-index

내 풀이

def count_h(mid, citations):
    for i in range(len(citations)):
        if citations[i] >= mid:
            return len(citations) - i
    return 0

def solution(citations):
    citations.sort()
    left, right = 0, max(citations)
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        h_count = count_h(mid, citations)

        if h_count >= mid:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    return answer

가능한 H-index는 0부터 max(citations)이니 이분탐색으로 풀었다.
count_h는 mid번 이상 인용된 논문의 개수를 반환하는데 정렬되어있으니 citations[i]가 mid이상인 순간 그 뒤의 것은 모두 mid 이상인 점을 이용했다.

0개의 댓글