[고득점 Kit / 정렬] H-Index

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

 

H-Index가 무엇인지 잘 이해해야 한다. 문제를 읽어보면 논문  n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 H-index라고 명시되어 있다.

 

쉽게 말해, h번 이상 인용된 논문이 h편 이상일 때, h의 최댓값을 찾는 문제이다. 따라서, 코드를 작성해보면 아래와 같다.

 

def solution(citations):
    # 1. 논문 인용 횟수를 내림차순으로 정렬
    citations.sort(reverse=True)  # [6, 5, 3, 1, 0]
    
    # 2. H-Index를 찾는 과정
    for i in range(len(citations)):
        if citations[i] <= i:  # citations[3] <= 3
            return i  # 3 반환
    
    # 3. 모든 논문이 i번 이상 인용된 경우
    return len(citations)

 

• citations.sort(reverse=True)를 통해 논문의 인용 횟수를 내림차순으로 정렬한다.
• 인덱스 i와 인용 횟수 citations[i]를 비교하여 citations[i] <= i가 되는 순간, 그때의 i 값이 H-Index가 된다. ( citations[i] <= i가 성립하는 순간, 인덱스 i 이후의 모든 논문은 인용 횟수가 i번 이하)
  • 이 조건이 성립되면 그 이상의 논문은 인용 횟수가 점점 줄어들기 때문에 더 큰 H-Index는 존재하지 않는다.
• 만약 모든 논문이 i번 이상 인용되었다면, 전체 논문의 수인 len(citations)가 H-Index가 된다.

 

그렇다면 h번 이하 인용되었다는 조건은 고려하지 않아도 되느냐? 라고 질문을 할 수 있다. 이러한 경우는 테스트케이스를 예로 들어 생각해보자. 

 

문제에 나와있는 테스트 케이스를 따라 논문의 인용 횟수가 [6, 5, 3, 1, 0]로 정렬된 상황을 가정해보자.

• i = 0: 6번 인용, h = 1 조건 만족 (계속 진행)
• i = 1: 5번 인용, h = 2 조건 만족 (계속 진행)
• i = 2: 3번 인용, h = 3 조건 만족 (계속 진행)
• i = 3: 1번 인용, 이때 citations[3] = 1인데, i = 3이므로 조건 불충족 -> 여기서 멈추고 H-Index는 3.

 

citations[i] <= i가 되는 순간, 해당 논문을 포함한 나머지 논문들은 인용 횟수가 감소하는 방향으로 정렬되어 있다. 즉, i번째 이후의 논문들은 그 인덱스 이상 인용된 논문이 더 이상 없다는 것을 의미한다. ( citations[i] <= i가 성립하는 순간, 인덱스 i 이후의 모든 논문은 인용 횟수가 i번 이하 ) 따라서 첫 번째 조건을 만족하는 시점에서 두 번째 조건도 자연스럽게 충족된다.