[프로그래머스] H-Index level2 - python

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

프로그래머스

 

 

 

 

 

 

 

 

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다.

 

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

 

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

 

 

 

 

 

 

 

 

 

 

제한 사항

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

 

 

 

 

 

 

 

 

입출력 예

 

 

 

 

 

---

이 문제에 나오는 h-index에 대한 개념을 알아야 한다.

 

입출력 예를 보면 총 5장의 논문이 있고 조회수가 [3, 0, 6, 1, 5] 로 구성되어 있다. 이때 4가 h-index 인지 판별해보면 조회수가 4 이상인 논문은 [6, 5] 즉, 2장이 존재한다. 만약 h-index가 4라면 2장이 아닌 4장 이상 존재해야하기 때문에 4는 h-index라 볼 수 없다.

 

3의 경우를 보면 조회수가 3이상인 논문은 [3, 6, 5] 로 총 3장이기 때문에 3장 이상 존재한다. 이럴 경우 3은 h-index가 될 수 있다. 물론 최종적으로 h-index의 후보들 중 가장 큰 수 하나가 h-index가 된다.

 

 

 

 

 

 

def solution(citations):
    sort_li = sorted(citations)
    
    a = []
    for h in range(1, len(citations)+1):
        if len([i for i in sort_li if i >= h]) >= h:
            a.append(h)
            
    return max(a)

위 코드는 h-index가 될 수 있는 모든 수를 초기화해두었던 a 리스트에 모두 append 시켜준 후 최대값을 return하는 코드이다. 하지만 이 코드는 시간복잡도가 커져 효율성 부분에서 떨어진다.

 

 

 

 

 

def solution(citations):
    answer = 0
    c = sorted(citations,reverse=True)
    for j in range(len(citations)):
        if j+1<=c[j]:
            answer+=1
    return answer

시간 복잡도 면을 해결하기 위해 대소 비교를 하여 h-index를 찾았다. 먼저 citations를 내림차순으로 정렬시킨 후 j번째의 논문 조회수가 j+1 이상인지 확인 후 만족할 경우 1씩 더해 h-index를 구하였다.