[프로그래머스] H-index

문제 이해하기

 H-index를 찾는 문제로, h-index는 n번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용됐다면 h의 최댓값이 이 과학자의 H-index입니다

 

예를들면[3 0 1 6 1 5]가 있다면 3이 h-index가 됨

주의할 점은 배열에 있는 값만 h-index가 되는게 아니기 때문에 최대 값을 기준으로 h-index(0 1, 2, 3, 4, 5, 6)를 탐색해야 합니다.

문제 해결 방법 설명하기

1. 정렬

h번 이상 인용된 논문이 h개 이상이라는 것을 찾기 위해서 정렬을 수행했습니다. 이는 특정 인덱스를 기준으로 이후에 나오는 값은 모두 특정 인덱스의 값보다 크기 때문에 h번 이상이라는 것을 찾기가 쉽습니다.

    citations.sort()  #정렬한 후 
    max_reference = max(citations)
    
    for i in range(max_reference + 1):
        idx = bisect.bisect_left(citations, i)    
        
        if i <= len(citations) - idx: #찾아진 인덱스의 값을 이용해서 h번 이상인지 판별함
            answer = i

 

 

2. 이분탐색으로 찾기

이분탐색을 사용한 이유는 배열에서 특정 값을 빠르게 찾을 수 있기 때문입니다. 

    for i in range(max_reference + 1):
        idx = bisect.bisect_left(citations, i)  #citations 배열에서 i번 이상 인용된 논문의 값이 이상이 되는 최초의 인덱스를 찾음 
        
        if i <= len(citations) - idx:
            answer = i
        
    return answer

 

 

코드

import bisect

def solution(citations):
    answer = 0
    
    citations.sort()
    max_reference = max(citations)
    
    for i in range(max_reference + 1):
        idx = bisect.bisect_left(citations, i)    
        
        if i <= len(citations) - idx:
            answer = i
        
    return answer


if __name__ == "__main__":
    citations = [3, 0, 6, 1, 5]
    solution(citations)

 

코드 리뷰

def solution(citations):
  sorted_citations = sorted(citations, reverse=True)
  for i in range(len(sorted_citations)):
    if sorted_citations[i] <= i: 
      return i
  return len(sorted_citations)

 

배운점 정리하기