99클럽 코테 스터디 25일차 TIL / h-index-ii

h-index-ii

학습 키워드: 이분탐색
문제 링크: https://leetcode.com/problems/h-index-ii/description/

문제 설명

주어진 정수 배열 citations에서 citations[i]는 연구자가 i번째 논문에서 받은 인용 수를 나타냅니다. 이 배열은 오름차순으로 정렬되어 있습니다. 연구자의 h-지수를 구하세요.

위키백과에 따르면, h-지수는 적어도 h번 인용된 논문이 h편 이상이고, 나머지 논문은 h번 이하로 인용된 논문 중 최대값 h로 정의됩니다.

로그 시간(logarithmic time) 내에 실행되는 알고리즘을 작성해야 합니다.

제한 조건

• n == citations.length
• 1 <= n <= 105
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

문제 풀이

배열에 인덱스로 접근해서 인덱스와 element값을 비교함. 문제의 조건에 ascending order라고 적혀 있기 때문에 정렬할 필요 없이 이분탐색 진행

class Solution:
    def hIndex(self, citations):
        n = len(citations)
        left, right = 0, n
        while left < right:
            mid = (left + right) // 2
            if citations[mid] >= n - mid:
                right = mid
            else:
                left = mid + 1
        return n - left

        

코멘트

log(n)의 복잡도로 풀어야 하기에 이분탐색 적용