문제 설명
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 | return |
|---|---|
| [3, 0, 6, 1, 5] | 3 |
풀이
def solution(citations):
citations.sort(reverse=True)
for i in range(len(citations)):
if citations[i] < i + 1:
return i
return len(citations)해결 과정
H-Index
우선, 이 문제에서 요구하는 H-Index 자체에 대해 이해하는 데도 오랜 시간이 필요했다. 그래서 일단 내 방식대로 이해한 것을 알려주고자 한다.
위에 언급된 입출력 예를 토대로 설명하면......
- 1번 이상 인용된 논문은 1편 이상이다. - [3, 6, 1, 5] - true
- 2번 이상 인용된 논문은 2편 이상이다. - [3, 6, 5] - true
- 3번 이상 인용된 논문은 3편 이상이다. - [3, 6, 5] - true
- 4번 이상 인용된 논문은 4편 이상이다. - [6, 5] - false
고로, h는 1, 2, 3이 가능한데, 이 중 가장 큰 값인 3이 바로 이 사람의 H-Index가 되는 것이다.
정렬
위에서 언급한 것처럼 1부터 시작해서 일일이 배열의 길이와 비교해 가장 큰 h를 구할 수도 있지만, 정렬을 사용하면 더욱 간편하게 계산할 수 있다는 것을 알아냈다.
입출력 예에 있는 배열을 "내림차순"으로 정렬해보자. [6, 5, 3, 1, 0]이 된다. 배열에서 요소를 하나씩 꺼내서 1, 2, ...과 비교해보자.
- 6은 1 이상인가? - true
- 5는 2 이상인가? - true
- 3은 3 이상인가? - true
- 1은 4 이상인가? - false
가장 마지막에 true로 판정된 것이 h = 3일 때다. 그러므로 H-Index는 3이 된다.
어떻게 이게 성립하는가?
내림차순으로 정렬을 하면 자신 이상의 값을 가진 요소들은 모두 자신의 왼쪽(인덱스 값 상 작은 쪽)에만 존재하는 특징이 있다.
그러므로 h가 x라고 할 때, 인덱스 (x - 1)번에 위치한 요소의 값이 x 이상이어야 h가 성립할 수 있다. 그 이유는 예를 들면서 설명하도록 하겠다.
[6, 5, 3, 1, 0]에서 h = 3이라 하자. 그렇다면 "3번 이상 인용된 논문은 3편 이상"이어야 한다. 배열에서 인덱스 2번에 위치한 값은 '3'이다. 즉, 해당 배열에서 3 이상의 값은 자신을 포함해 3편 이상이 있다는 뜻이다. h = 3이므로 조건을 만족한다.
그러면 h = 4라고 하자. 이 경우, "4번 이상 인용된 논문은 4편 이상"이어야 한다. 배열에서 인덱스 3번에 위치한 값은 '1'이다. 이 경우, 4번 이상 인용이 아니라 1번 이상 인용이 4편인 것이다. 그러므로 h = 4 조건을 부합시킬 수 없기 때문에 H-Index는 4 - 1, 3이 된다.
예외 상황
다만, 내 풀이에서는 한 가지 예외 상황을 생각할 수 있다. 바로, "배열 내 모든 요소가 배열의 길이 초과의 값을 지닌 경우"다.
예를 들어, [5, 8, 7]의 경우 배열 길이 "3" 이하의 값은 배열 내에 없다. 이렇게 되면 반복문을 돌려도 if citations[i] < i + 1의 조건을 만족하는 경우가 없기 때문에 반복문이 그대로 종료된다.
그렇다면, 위 경우는 배열 길이(예시에서는 3)가 h가 된다. 왜냐하면 h는 배열의 길이보다 큰 값을 가질 수는 없기 때문이다(h번 이상 인용된 논문이 h편이어야 하는데, 배열 길이보다 큰 수를 가지면 h편 이상의 조건을 만족할 수 없다).
그러므로 이 경우에는 배열 길이를 반환해주면 된다.
다른 사람의 풀이
def solution(citations):
citations = sorted(citations)
l = len(citations)
for i in range(l):
if citations[i] >= l-i:
return l-i
return 0나와는 반대로 "오름차순"으로 정렬하고, 전체 길이에서 현재 인덱스를 빼는 방식으로 계산했다.
이 경우도 마찬가지로 l - i가 h번 이상을 의미하므로, 해당 값 이상이 나오게 된다면 l - i가 가장 큰 h이므로 H-Index가 된다.
다만, 이 경우는 H-Index가 0이라면 반복문에서 조건이 걸러지지 않으므로 반복문이 return문에 의해 종료되지 않았다면 0을 반환한다.
