문제

🔗 정렬 | H-Index

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회 이하입니다.

내가 작성한 코드

def solution(citations):
    citations.sort()
    for h in range(max(citations), 0, -1):
        overh = 0

        for citation in citations:
            if citation >= h:
                overh += 1

            if overh == h:
                return h
    return 0

다음의 순서에 따라 풀이했다.

1. citations배열을 정렬해준다.

citations.sort()

사실 배열을 정렬을 해주지 않아도 통과된다. 실행시간이 약간 내려가지만 미미하다. (시간복잡도도 공부를 해야겠다..)

2. max(citations)부터 0까지 -1하면서 검사한다. 각 논문들이 h편 이상 인용되었는지 확인하기위해 overh를 0으로 초기화해준다.

for h in range(max(citations), 0, -1):
        overh = 0

3. citations배열 안에있는 citation마다 citation이 h편 이상 인용되었다면 overh += 1을 해준다. 그리고 overh가 h 값과 같아졌다면 h를 리턴한다.

...
	for citation in citations:
            if citation >= h:
                overh += 1

            if overh == h:
                return h
	return 0

이때, 마지막 줄에 return 0가 없다면 테스트 16이 통과되지 않는다. citations이 [0,0,0]처럼 0만 담겨있다면 2번에서 실행되지 않아 null이 리턴된다. 이 경우를 막기위해return 0를 추가해 통과할 수 있었다.

어마어마한.. 시간복잡도........

다른 사람의 풀이

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