Sort - H-Index

처음 알았지만, 과학자들의 논문의 생산성을 나타내는 H-index라는 것이 있다고 합니다.

programmers.co.kr/learn/courses/30/lessons/42747?language=python3

코딩테스트 연습 - H-Index

 

H-index는 과학자가 N편의 논문을 발생했을 때

 

h번 이상 인용된 논문이 h편 이상이라고 합시다.

 

이때 h는 0~Max_cit(과학자의 최대 인용 논문 인용수)만큼의 값 사이에서 존재하게 됩니다.

 

이때 h의 유효한 최대값이 H_index가 됩니다.

 

예를들어서, 5개의 논문이 각각 [3,0,6,1,5] 번 인용되었다고 한다면

 

3개의 논문(1,3,5번째 논문)이 3번 이상(각각 3,6,5)번 인용되었고

 

4번 이상인용된 논문이 2개가 되기 때문에, 3이 h의 최대값이 되게 됩니다.

(이 부분을 추가함으로 찾아야할 경우의수를 줄이기 때문에 알고리즘 성능이 향상됩니다.)

 

H_index를 구하기 위한 알고리즘으로는

1. Max_cit(논문중 가장 많이 인용된 논문의 인용 수)를 구한다

2. cit_count(논문의 총 개수)

3. 논문 목록을 인용 횟수에 따라 정렬

4. i(0~Max_cit) 사이에서 인용횟수가 i번 이상인 논문의 갯수를 Count

4_1. i번 이상인 논문의 갯수가 i이상이면 h_index를 i로 갱신

5. i가 인용횟수가 i번 이상인 논문의 갯수 보다 작을경우 더이상 해가 없으므로 알고리즘 종료

 

5번 Sequence의 유무에 따라서 알고리즘 수행시간이 약 100배이상 차이가 나게됩니다.

 

H_index를 구하기위한 Solution을 Python으로 작성한 예시입니다 :)

#ex citations = [3, 0, 6, 1, 5]
def solution(citations):
    answer = 0
    #입력값을 통해서 가장 많이 인용된 횟수, 논문의 총 개수를 산출
    max_cit_num = max(citations)
    cit_count = len(citations)
    #5번 Early Strop을 위한 Validation 항목 
    validation = False
    #논문 리스트를 인용 횟수를 기준으로 정렬
    citations.sort()        
    #0~Max_cit 사이에서
    for i in range(max_cit_num):
    	#인용수가 작은 논문부터 순차적으로 탐색
        for j in range(cit_count):
        	#5번 Seq에 해당하며
            #h이상 인용된 논문의 수가 h보다 작을경우 더이상 해가 없으므로
            #validation을 True로 바꿔주어 반복문은 Early Stop해줍니다.
            if ((cit_count+1)-j<i):
                validation = True 
                break            
            #논문의 인용수가 i(0~Max_cit 사이의 탐색값)보다 클 경우
            #i 이상의 논문수를 Count하여 H_index를 갱신합니다.
            if (citations[j]>=i):
                if (cit_count+1)-j>i:
                    answer = i
                    break
        #5번 Seq를 통해서 Early Stop이 가능할 경우
        #빠르게 반복문을 종료 후 결과값을 반환합니다.
        if validation:
            break
    return answer