[프로그래머스] (정렬) - 42747 H-Index

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citations	return
[3, 0, 6, 1, 5]	3

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

---

풀이

# 이진탐색을 활용한 풀이

def solution(citations):
    answer = 0
    citations.sort() # citations 오름차순 정렬
    n=len(citations) 
    
    # 이진 탐색을 위한 start, end 값 지정
    start=0 
    end=citations[-1]
    
    while(start<=end):
        mid=(start+end)//2
        
        # 배열 앞에서 부터 mid 보다 큰 값 탐색 후, 찾으면 index에 저장 후, break
        for idx in range(len(citations)):
            if citations[idx]>=mid: 
                index=idx
                break
        
        # n-index는 mid번 이상 인용된 논문 수
        # index는 나머지    
        
        # mid가 n-index 즉, n편 중 mid번 이상 인용된 논문이 mid 이하일 때,
        # 그리고 그 외 나머지 즉, index가 mid 번 이상일 때 end를 mid-1로 줄임
        if n-index<mid or index>mid:
            end=mid-1
        else: # 문제 조건에 맞을 경우 최댓값을 구해야하므로 answer에 저장하고 start를 늘려 계속 구해본다.
            answer=mid
            start=mid+1
    
    return answer


# print(solution([3, 0, 6, 1, 5]))

 

Reference

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스