[알고리즘/정렬] 프로그래머스 - H-Index

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

프로그래머스

 

📌문제설명 

• H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
• 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
• 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 

 

제한사항

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

만일 citations가 [3,0,6,1,5] 라고 했을 때, 여기서 과학자가 발표한 논문의 수는 총 5편이고, 그 중 3편이 3회이상 인용되었으며 나머지 2편의 논문이 3회 이하 인용되었다. 때문에 이 과학자의 H-Index는 3이다. 

 

📌풀이 아이디어 

 

파이썬의 이진탐색 알고리즘을 사용하면 편할 거 같아서 들고왔다. (안외우고 있어서 보고왔따...) 

from bisect import bisect_left 

a = [ 1, 2 , 4 ,4, 8] 
x = 4 

print(bisect(a,x)) 

#실행결과 
2

 

정말 문제 그대로 n편 중 h회 이상 인용된 논문이 h편 있는 경우, h의 최대값을 구하고자 했다. 

h회 이상 인용된 논문의 개수 = 전체 배열의 길이 - bisect_left(배열 , h) 를 활용하여 구했다. 

 

1. 우선은 주어진 배열을 오름차순으로 정렬한다.      

2.  배열의 중간 숫자로 시작점 설정 . 

3.  전체 배열길이 - bisect( 배열 ,  중간위치숫자) 가 만일 중간숫자보다 같거나 크다면 h-index 최대값 업데이트

4. start = mid+1로 설정 후 다시 탐색하여 업데이트

5. 만일  전체 배열길이 - bisect( 배열 ,  중간위치숫자) 가 중간숫자보다 작다면 end = mid-1로 설정 후 다시 탐색 

 

예를 들어 [3,0,6,1,5] 주어진다고 해보자. 

 

1. 오름차순으로 정렬 

[ 0 1 3 5 6 ] 

 

2. h-index 시작점 설정 

mid = start + end // 2 = 5 //2 = 2 

 

3. 배열길이 - bisect(배열,2)  = 5- 2= 3 

 

해당 의미는 전체 5개의 논문 중 2회 이상 인용된 논문은 3개라는 의미 

3은 2보다 크므로 h-index는 2로 업데이트 후 start += 1 하여 다시 mid값 설정 

 

mid = (start + end) // 2 = 1+5 // 2 = 3 

 

해당 의미는 전체 5개의 논문 중 3회 이상 인용된 논문은 3개라는 의미 

3은 3과 같으므로 h-index는 3로 업데이트 후 start += 1 하여 다시 mid값 설정 

 

mid = (start + end) // 2 = 2+5 // 2 = 3 

 

위 과정과 동일하게 계속 진행 

 

mid = (start + end) // 2 = 3 +5 // 2 = 4 

 

배열 길이 - bisect(배열 , 4) = 5 - 3 = 2 

해당 의미는 전체 5개의 논문 중 4회 이상 인용된 논문은 2개라는 의미이다. 이 경우 조건에 해당되지않으므로 다시 mid 값을 조정한다. => end -= 1 

 

start가 end보다 커지지 않을 때 까지 반복 후 max_h값 return 

 

📌 최종코드 

from bisect import bisect_left

def solution(citations):
    # 오름차순 정렬
    citations.sort()
    
    n = len(citations)
    start , end = 0 , n
    max_h = 0 #h값 초기화 
    
    while start <= end : 
        h = start + end // 2
        if h <= n - bisect_left(citations, h):
            max_h = max(max_h , h)
            start += 1 
        else :
            end -= 1 
    
    return max_h

 

📌 다른사람코드 풀이

나는 bisect 라이브러리 까지 끌고와서 풀이했지만, 정말 단순한 코드로 풀이가 가능한 문제였다.. 

 

index	1	2	3	4	5
citations	6	5	3	1	0

 

우선, 인용횟수를 내림차순으로 정렬한다.  만일 인덱스보다 인용횟수가 크다면 인덱스+1 을 해준다.

이 경우에는 h-index 조건을 만족하는 경우이다. 처음부터 현재까지의 논문이 그 index 이상으로 인용이 된다는 것과 동일한 의미입니다.   해당 단계를 반복하다가 인용횟수보다 인덱스가 크다면 반복을 멈추고 인덱스를 return 한다.   
(만일 h-index가 4가 될려면 처음부터 index가 4까지의 논문의 인용횟수가 모두 4이상이였어야 한다. ) 

 

def solution(citations):
    # 논문 인용 횟수를 내림차순으로 정렬합니다.
    citations.sort(reverse=True)
    
    # H-Index를 찾기 위해 인용 횟수와 인덱스를 비교합니다.
    h_index = 0
    for i, citation in enumerate(citations):
        if citation >= i + 1:
            h_index = i + 1
        else:
            break
            
    return h_index