[Programmers_python] H-index

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

프로그래머스

내 풀이방식

def solution(citations):
    h = len(citations)
    citations = sorted(citations, reverse = True)
    # print(citations)
    if h == 1:
        return 1
    while True:
        for i in range(len(citations)):
            if citations[i] < h and i < h:
                h -= 1
                break
            elif citations[i] < h and i >= h:
                return h

처음 이 문제를 풀었을 때, h를 citations 리스트 길이로 정해두고 h가 가능한 값이 될 때까지 h를 1씩 줄이는 방식으로 구현을 했다. 그러다보니 예상은 했지만 몇개의 테스트케이스에서 시간초과가 발생했다. h를 1씩 줄이는 것이 아니라 더 좋은 방식으로 줄이면 될 것 같다는 생각에 여러 방식으로 시도했지만 실패했다,,,,

 

정답 풀이

def solution(citations):
    citations = sorted(citations, reverse = True)
    for i in range(len(citations)):
        if citations[i] <= i:
            return i
    return len(citations)

• citations를 내림차순으로 정렬
• 0부터 len(citations)-1까지 반복하여 citations[i]와 i를 비교한다. $\rightarrow$ citations[i]가 i보다 작거나 같은 i를 찾으면 그 i가 최대의 h값이 된다!!
• 반복문 동안 h를 찾지 못하면 citations 리스트의 길이가 최대의 h가 된다! $\rightarrow$ 모든 리스트의 원소들 (인용된 횟수들) 이 리스트의 갯수 (논문의 수)보다 항상 커서 h의 최대값이 논문의 수와 같아진다!

어렵지 않은 문제인줄 알았지만 한부분을 생각을 못하면서 시간이 엄청 걸렸던 문제였다,,ㅜㅜ