[프로그래머스/파이썬] (정렬) 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
    cit = sorted(citations)
    if cit[-1] != 0:
        for i in range(1, len(cit)+1):
            if cit[-i] >= i:
                answer = i
            else: break
    return answer

citations를 정렬해서 n-h+1 번째 값이 h 이상이면 h편 이상이 h번 이상 인용됐다고 볼 수 있다.
그리고 h의 최댓값이 예를 들어 h1이라고 한다면 h1-1에 대한 위 문장도 성립한다는 것을 알 수 있다.
따라서 if문 안에서는 h에 해당하는 i를 1씩 증가시켜서 cit[-i] 와 i를 비교한다.
좌변이 같거나 크다면 cit[-i:]의 i개 요소가 i 이상이라는 뜻이므로 answer에 i를 대입한다.
만약 우변이 더 크다면 현재의 answer이 h의 최댓값이다.

정확성 테스트: ~0.24ms / 10.3MB

풀이는 어렵지 않게 구현할 수 있지만 나는 여기서 조금 더 간결한 코드를 만들고 싶었다.

간결한 풀이

def solution(citations):
    cit = sorted(citations)
    return max([x for x in range(len(cit)+1) if cit[-x] >= x])

이 코드는 본래의 코드와 정확히 같은 풀이를 따라가지만 훨씬 간단해보인다.

정확성 테스트: ~0.27ms / 10.4MB

다른 풀이

다른 사람들의 풀이를 보다가 굉장한 코드가 있어서 가져왔다.

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

enumerate한 것을 리스트 형태로 바꿔준다.

index of (i+1,citations[i]), i	0	1	2	...	h-1	...
i+1	1	2	3	...	h	...
citations[i]	citations[0]	citations[1]	citations[2]	...	h	...
min(i+1,citations[i])	1	2	3	...	h	...

citations에 대해서는 내림차순 정렬을 했기 때문에 만약에 최댓값이 h라면 위 표에서 citations[:h]의 모든 원소는 h보다 같거나 크다.
하지만 index i가 0~h-2일 때 i+1은 모두 h보다 작으므로 min 값 또한 h보다 작다.

i가 h 이상일 때는 citatations[i]가 h보다 같거나 작다.
혹여 크다면 min 값이 h보다 커질 것이기 때문에 h가 최댓값이 아니다.

따라서 enumerate(citations, start=1)에 min 함수를 씌워서 max값을 구하는 것은 h의 최댓값을 구하는 것과 같다.

정확성 테스트: ~1.00ms / 10.3MB