[프로그래머스] 'H-index' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]

---

 

문제 설명

 

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

알고리즘 분석

 

• 나의 풀이

def solution(cit):
    cit.sort() # 숫자를 작은 순서로 정렬 
    for idx, c in enumerate(cit): # index와 요소의 값
        if c >= len(cit[idx:]): # cit의 요소가 cit[idx:]보다 크거나 같을 경우  
            return len(cit[idx:]) # h-index를 반환 
    return 0 

 

지문에서 h-index에 대해 요구하는 조건은 다음과 같다. 

 

1. 모든 논문 n 편 중,
2. h번 이상 인용된 논문이 h편 이상 
3. 나머지 논문이 h번 이하 인용 
4. h의 최댓값이 H-index 

이 조건을 처음 봤을 때는 h가 3번 들어가서 뭐가 뭔지 헷갈렸었다. 

 

그래서 다음과 같이 쉽게 풀어보았다. 

 

우선 "cit = [2, 5, 4, 10, 30, 9, 11, 7]"라고 가정해보자. 

 

1. h번 이상 인용된 논문이 h편 이상 

 h의 값은 무조건 "len(cit)"보다 작다는 것을 의미한다. 

위의 cit의 최댓값은 30이다. 그것을 h에 대입해보면 

• 30번 이상 인용된 논문이 30편 이상 : 여기서 "논문"의 수는 "cit"의 길이와 같다. 그렇다는 말은 h가 len(cit) 보다 큰 경우는 절대 없다는 의미다. 즉, h의 범위는 0부터 len(cit)까지이므로 논문이 30편 이상일 경우는 절대 없다. 

그리고 착각할 수 있는 부분이 있는데, 

난 처음에 cit의 요소만 h가 될 수 있는줄 알았지만 h는 0부터 len(cit) 사이의 정수이기만 하면 된다. 

 

2. 나머지 논문이 h번 이하 인용

 이 부분은 지문을 어렵게하는 함정인 것 같다. 

h번 이상 인용한 논문을 전부 구했을 경우, 나머지 논문은 필연적으로 h번 이하로 인용된다. 

즉, 이 부분은 신경쓰지 않아도 상관없다. 

 

3. if c >= len(cit[idx:])

위처럼 비교하는 이유를 "cit = [2, 5, 4, 10, 30, 9, 11, 7]"로 설명하자면

C	부호	len(cit[idx:]) = h	참 or 거짓	해석
2	>=	8	False	2이상인 요소가 8개
4	>=	7	False	4이상인 요소가 7개
5	>=	6	False	5이상인 요소가 6개
7	>=	5	True	7이상인 요소가 5개

 

위의 표에서 C는 cit의 요소, len(cit[idx:])는 C이상인 요소의 개수를 나타낸다. 

지문에 따르자면 C는 "논문이 인용된 횟수", len(cit[idx:])는 "C 이상 인용된 논문의 개수"이다. 

 

위의 표에서 len(cit[idx:])의 값을 보면 알겠지만 h-index가 가질 수 있는 최댓값부터 시작해서 1씩 줄어들고 있다. 

그리고 C가 len(cit[idx:])보다 커지면 True를 리턴하고 결과적으로 len(cit[idx:])를 h의 최댓값으로 리턴한다. 

최종적으로 h-index는 5가 된다. 

 

아직 이해가 안 된다면

h =5일 경우와 h = 7일 경우를 비교해보면 된다.

 

• h = 5일 경우 : (요구조건) 5 이상인 요소가 5개 이상 : (조건 만족) 5 이상인 요소가 6개
• h = 7일 경우 : (요구조건) 7 이상인 요소가 7개 이상 : (조건 불만족) 7 이상인 요소가 5개 

위에서 확인한 것처럼 5 이상인 요소가 5개 이상일 경우에 h가 될 수 있는데

우리는 반복문을 거치며 이미 조건이 만족하는 것을 확인했다. 

만약 C의 값 중에 h가 없더라도 요구조건을 만족하는 가장 큰 h-index 값을 얻을 수 있다. 

 

 

마치며....

솔직히 이런 문제는 금방 풀 수 있을 줄 알았는데 

누가 만들었는지는 몰라도 은근히 골머리를 앓게 만든 문제였다. 

 

 

 

코딩테스트 연습 - H-Index