99클럽 코테 스터디 17일차 TIL Leetcode H-Index II

Leetcode H-index2

H-index 문제, 프로그래머스에도 있는 문제이다.

다른점은 이미 오름차순으로 정렬되어있어 더 빠르게 찾기만 하면 된다.

2가지 방법이 있는데, 하나는 순차적으로 탐색하며, 비교하는 방법이며, 다른 하나는 이분탐색을 활용한 방법이다.  

결과적으로 말하면 둘중 어떤 알고리즘이든 index가 1일때 자기포함 뒤에 있는 갯수가 해당 index의 citations 값보다 크거나 같은지 확인하면서 찾아가면 된다.

나의 코드

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n=len(citations)
        l,r=0,n-1
        while l<=r:
            mid=(l+r)//2
            if citations[mid]<n-mid:
                l=mid+1
            elif citations[mid]>=n-mid:
                r=mid-1
        return n-l