Level 2 H-Index Python3

https://programmers.co.kr/learn/courses/30/lessons/42747?language=python3 

코딩테스트 연습 - H-Index

 

최종 풀이

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_H-Index.py

hwayeon351/Programmers-Algorithms

def solution(citations):
    citations.sort(reverse=True)
    for i, h in enumerate(citations):
        if i+1 < h: continue
        elif i+1 == h: return h    
        elif i+1 > h: return i
    return len(citations)

---

풀이 과정

이전에 풀었던 문제를 다시 한 번 풀어봤는데 어려웠다.

이 문제 역시 문제에 힌트가 숨어있었는데 바로 h의 최댓값이 H-Index라는 점과 논문 수는 최대 1000편이라는 점이다.

처음에 나는 citations를 정렬한 후 중간값을 기준으로 h값을 조정해나가는 방식으로 구현하려 했었다.

그런데 논문 수가 최대 1000편이라는 점에서 citations를 정렬한 뒤 가장 큰 값부터 차례대로 h가 될 수 있는지 따져보면 시간 복잡도는 T(n)가 되고 n의 최댓값이 1000이기 때문에 H-Index를 구하는데 크게 무리가 없다.

 

def solution(citations):
    citations.sort(reverse=True)
    for i, h in enumerate(citations):
        if i+1 < h: continue
        elif i+1 == h: return h    
        elif i+1 > h: return i
    return len(citations)

#논문 수 최대 1000편 내림차순으로 하나씩 순회 가능
#1.h가 i+1보다 큰 경우 -> h번 인용된 논문이 h편보다 작다.  => h가 더 작아야 한다.
#2.h가 i+1과 같은 경우 -> h번 인용된 논문이 h편 있다. => return h
#3.h가 i+1보다 작은 경우 -> h가 최대값이 아니다. => 이 경우 i번 이상 인용된 경우가 최대 h값이다. return i
#4.모든 citations의 논문이 1.조건에 걸려 for문을 벗어난 경우 -> return len(citations)

#2. 6,5,3,1,0 -> 3
#2. 100,100,100,4,0 -> 4
#3. 100,100,100,0,0 -> 3
#4. 100,100,100,100,100 -> 5

#시간복잡도 = O(nlogn), 공간복잡도 = O(n)

현재 h값을 기준으로 다음과 같은 기준을 따져줘야 한다.

1. 현재 h값의 idx+1이 h보다 작은 경우(h값이 될 수 없는 경우)

 이 경우는 해당 h값이 더 작아져야 함을 의미한다. citations을 내림차순으로 정렬했기 때문에 idx+1이 h번 인용된 논문의 수가 된다. 따라서, 이 경우는 h번 인용된 논문이 h편보다 작은 경우이다.

 

2. 현재 h값이 idx+1이 h와 같은 경우(h값이 H-Index가 된다.)

 citations을 내림차순으로 정렬했기 때문에 idx+1이 h와 같다는 것은 h번 인용된 논문의 수가 h개 있다는 것이다. 이 경우가 h값 중 최댓값이므로 H-Index이다. 예를 들어 citations = [100, 100, 100, 4, 0]인 경우 h값이 4일 때 idx+1 = 4이므로 현재 h값이 H-Index가 된다.

 

3. 현재 h값이 idx+1보다 작은 경우(h값이 맞지만 최댓값이 아니므로 H-Index가 아니다.)

 h번 이상 인용된 논문 수가 idx+1개 있지만, h < idx+1이므로 idx+1이 H-Index가 된다. 예를 들어 citations = [100, 100, 100, 0, 0]인 경우 h값이 0일 때, idx+1 = 4이므로 4가 H-Index가 된다.

 

4. 모든 citations의 항목이 1.조건에 걸려 for문을 벗어난 경우

 citations의 항목 수가 H-Index가 된다. 예를 들어 citations = [100, 100, 100, 100, 100]인 경우, 1.조건에 걸려 for문을 벗어나게 되는데 이때 H-Index는 5가 되야하고 len(citations) = 5임을 알 수 있다.