프로그래머스 정렬 Level 3: H-Index 알고리즘 풀이

1. 문제 설명

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

입출력 예

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

2. 문제 이해

주어지는 citations 리스트의 요소에 대해서 n 이상인 값이 n개인 값의 최대값을 구하는 것으로,
주의해야 할 점은 citations 리스트 안에 있는 값만 해당되지 않는다.
즉, citations = [0, 3, 4]인 경우 결과 값은 2가 나올 수 있다는 것이다.
해당 문제의 질문을 살펴보니 대부분의 사람들이 이를 이해하지 못해, 사고가 좁아져 답을 도출해내지 못하고 있었다.

3. 문제 풀이

리스트 정렬

citations.sort()

• sort(): 주어진 값을 오름차순으로 정렬한다.
  sort 함수를 이용해 원래의 citations 값인 [3, 0, 6, 1, 5]에서 [0, 1, 3, 5, 6]으로 정렬한다.
  
  
  리스트의 특정 요소 값보다 큰 값의 개수

for i in range(citations[-1]):
        if i == sum(i <= x for x in citations):
            answer = i
            return answer
        if i <= sum(i <= x for x in citations):
            answer = i

• sum(i <= x for x in citations)를 하면 citations 리스트의 요소 중에서 i 보다 크거나 같은 값의 수가 나온다.

for i in range(citations[-1]):

• 우선 for문의 범위를 0부터 citations의 가장 큰 수인 citations[-1]값으로 준다. 이렇게만 하면 i는 0부터 시작해서 citations의 마지막 값이자, 가장 큰 수인 citations[-1] 값까지 증가하게 될 것이다.
• 그러고 나서, 리스트 요소 안의 값이 H-Index라면

if i == sum(i <= x for x in citations):
            answer = i
            return answer

• 위의 if문만 만들면 되지만 [0, 1, 2] 리스트의 H-Index 값은 1로, 1이상의 값이 2개로 위의 if문 조건에 해당하지 않는다. 이처럼 리스트 요소 안의 값이 H-Index가 되지 못한다면 H-Index 값을 찾아내지 못하게 된다.

if i <= sum(i <= x for x in citations):
            answer = i

• 그래서 위와 같이 i가 i개 이상인 것에 대한 if문을 만들어 answer에 i의 값을 넣어주었다.
  이렇게 한다면 리스트 요소 안에 H-Index 값이 없더라도 H-Index 값을 찾아낼 수 있게 된다.
  ※ 첫 번째 if문을 없애고 위의 if문만 사용해도 결과는 같지만 H-Index 값을 찾았을 때 바로 for문을 종료시키지 않는다면 시간복잡도 문제가 발생할 수 있기 때문에 첫 번째 if문을 사용하는 것을 추천한다.
  
  

  첫 번째 if문이 존재하는 경우
  첫 번째 if문이 존재하지 않는 경우
  
  

• 마지막으로 리스트가 [0,0,0]인 경우 for문에서 H-Index 값을 찾을 수 없기 때문에 answer 값은 0으로 초기화 해줘야 한다.

4. solution

def solution(citations):
    answer = 0
    citations.sort()
    for i in range(citations[-1]):
        if i == sum(i <= x for x in citations):
            answer = i
            return answer
        if i <= sum(i <= x for x in citations):
            answer = i
    return answer