[프로그래머스 - Level 2] H-Index

[출처] : https://programmers.co.kr/

문제

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과(https://programmers.co.kr/learn/courses/30/lessons/42747#fn1)에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예 설명

접근

문제를 잘 이해 해야된다

논문 n편중 h번 이상 인용된 논문이 h편 이상이다. 이말을 [20,19,18,2] 이 리스트를 가지고 설명해보겠다

논문 n편은 리스트의 크기인 4가 된다. 이중 h번 인용된 논문이 h편 이상일라면 답은 3이다

h편이상이다 라는 말은 h가 최대 리스트의 크기 까지 된다는 뜻이다

4부터 내려가보도록 하겠다.

⇒ 4번이상 인용된 논문이 4편이상이다. 이 경우 4번이상 인용된 논문은 20,19,18이므로 틀렸다

⇒ 3번이상 인용된 논문이 3편 이상이다. 이경우 3번이상 인용된 논문은 20,19,18이므로 답이다.

⇒ 2번 이상 인용된 논문이 2편이상이다. 이경우 20,19,18,2이므로 2편이상이지만 최대가 아니므로 틀렸다.

위의 예시들을 보면 만약 h의 횟수를 0편부터 올라가면서 구하면 h번 이상 인용된 논문이 h편이상이다라는 조건을 만족하지만 최대가 되는 h를 구하기가 복잡해진다.

h횟수를 최대치 부터 내려가면 처음으로 만족하는 h가 최대가 되기 때문에 위에서 부터 내려온다.

이문제를 해결하기 위해서 우선 배열을 오름차순으로 정렬해주었다. 그래야 0번째 인덱스 부터 비교했을때 조건에 맞으면 정렬되어있기 때문에 그 뒤의 인덱스는 볼필요가 없어진다

if citations[i]>=len(citations)-i: 이 문장이 논문 n편중 h번 이상 인용된 논문이 h편 이상이다를 코드로 쓴 결과이다

len(citations)-i 이것을 h라고 생각하면 된다.

예시를 [20,19,18,2]로 가정하고 해보도록하겠다.

정렬을 했으니 [2,18,19,20]이다

처음 i가 0 이면 2≥4 가 된다. 이는 만족하지 않는다

다음은 18≥4-1 이 되는데 이는 만족한다. 인덱스 1번이 h이상이면 배열이 정렬되어 있기 때문에 그 다음부터 전부 만족을 한다. 인덱스 자신을 포함한 끝까지의 수는 len(citations)-i 이게 된다.

즉 위의 예시에서 citations[1]이 4-1(len()citations -i)보다 크거나 같다는 조건을 만족하면 1부터 인덱스 끝인 3까지 모든 값은 정렬되어있으므로 모두 조건을 만족하고 이 크기는 3(len()citations -i)이된다.

따라서 조건을 만족했을때 len()citations -i 이것을 리턴해주면 조건을 만족하는 h의 최대값이 된다.

def solution(citations):
    answer = 0
    citations = sorted(citations)
    for i in range(len(citations)):
        if citations[i]>=len(citations)-i:
            return len(citations)-i
    return answer

결과