정렬_H Index_Python

문제 설명

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

※ 공지 - 2019년 2월 28일 테스트 케이스가 추가되었습니다.

---

접근 방법

무엇보다도 문제를 이해하는데 오래 걸린 문제였다.

위키 백과의 예제와 아래 블로그의 내용을 참고하면 이해가 더 빠르다.

참고: https://www.ibric.org/myboard/read.php?Board=news&id=270333 

[연구논문을 위한 핵심 10단계] H-지수(H-Index) 란 무엇인가?

출처 :   https://www.ibric.org/myboard/read.php?Board=news&id=270333  

결국 H인덱스의 기준이 되는 논문의 갯수가 중요하며, citations 안에 있는 요소는 크게 중요하지 않다.

정렬 후 n번째 인용횟수가 n보다 크거나 같은 경우만 횟수가 인정된다.

 

먼저 주어진 배열을 오름차순으로 정렬한다.

오름차순으로 정렬함으로써 일치하는 지점을 찾는 시점 이후로는 모든 조건 식을 만족하게 된다.

처음에는 굉장히 어렵다고 생각했지만, 문제를 이해한다면 충분히 풀 수 있다고 생각한다.

(프로그래머스 문제 설명을 읽으면 더 햇갈린다.)

 

아래의 예시가 H 인덱스를 이해하는데 더 도움이 될 것같다.

(테스트 케이스에 추가하는 것을 추천한다.)

발표한 논문 N개 중,

H번 이상 인용된 논문이 H개 이상이고 나머지 논문은 H번 이하로 인용되었다면 H의 최댓값이 H 인덱스이다.

 

현재 과학자는 2개의 논문을 발표하였으며 각 논문은 66회 32회 인용된 상태이다.

총 인용된 논문의 갯수 2개부터 시작한다.

여기서 H 인덱스는 절대 2보다 큰 값이 나올 수 없다.

이때 h를 가장 큰 값(논문의 갯수)로 가정하고 인덱스 변화에 따라 

각 논문의 인용횟수가 2보다 크거나 같은 지점을 찾는다.

오름 차순 정렬로 인해 인용 횟수 2와 32를 비교하며 당연히 32 이후로는 모두 조건을 만족하는 값이며

나머지 논문 0개는 2번 이하로 인용되었다 할 수 있기에 H 인덱스는 바로 2가 된다.

input = [66, 32] // return = 2 

 

이 문제의 중요 핵심은 문제의 이해와 assume_h가 아닐까 생각한다.

H 인덱스를 찾지 못한 경우에 대한 설명이 없다 함수를 종료만 시켰으나, 20번 테스트에서 실패한다.

def solution(citations):
    """
    정렬 후 n번째 인용횟수가 n보다 크거나 같은 경우만 횟수가 인정된다.
    """
    # 오름차순 정렬!
    citations.sort()
    # 논문의 총 개수
    num = len(citations)
    # print(citations)
    # [0, 1, 3, 5, 6]
    # 3
    
    for i in range(num):
        # 인용된 논문 개수 h개 == 인용된 횟수 h번 일치하는 지점을 찾는다.
        # 인용된 논문의 개수(h개 == h번) <= 논문이 인용된 횟수(h번 이상)
        # H인덱스를 가정! 하고 일치하는 지점을 찾는다.
        assume_h = num - i
        if assume_h <= citations[i]:
            return assume_h
    
    return

 

 

함수를 종료할때 단순 종료 또는 None 이 아닌 0을 대입하니 문제 없이 통과되었다.

def solution(citations):
    """
    정렬 후 n번째 인용횟수가 n보다 크거나 같은 경우만 횟수가 인정된다.
    """
    citations.sort()
    num = len(citations)

    
    for i in range(num):
        assume_h = num - i
        if assume_h <= citations[i]:
            return assume_h
    
    return 0

---

시간복잡도

파이썬의 Team sort => O(N log N)

논문의 갯수 만큼 반복하므로 O(N)

총 시간 복잡도는 O(N log N)

 

참고 : https://www.ibric.org/myboard/read.php?Board=news&id=270333 

[연구논문을 위한 핵심 10단계] H-지수(H-Index) 란 무엇인가?

h-index - Wikipedia

h-index - Wikipedia