[Python]Programmers H-Index(lv2)

1. 문제

 

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

프로그래머스

 

어떤 과학자가 발표한 논문 n 편중, h번 이상 인용된 논문이 h편 이상이고,

 

나머지 논문이 h번 이하로 인용되었을때 h의 최대값이 과학자의 H-Index가 된다.

 

어떤 과학자가 발표한 논문 n편의 인용 횟수가 담겨있는 배열 citations가 주어진다.

 

이 과학자의 H-Index는 얼마일까?

 

2. 풀이

고생해서 풀었는데 엄청 간단한 풀이가 있다는 것을 알게되어 허무했다.

 

나는 문제에 있는 조건을 모두 만족시키는 h를 완전탐색 O(n^2)하는 방법으로 풀었다.

 

우선 h번 이상 인용된 논문이 h편 이상이 되어야하므로, 0부터 시작해서 논문의 개수(len(citation))까지 i번 이상 언급된 논문이 총 몇개인지 세어준다,

 

이때 up_paper라는 함수를 만들었는데 citation 배열과 i를 매개변수로 전달받아 반복문을 통해 citation 내부를 돌면서 전달받은 i 이상의 논문이 몇개인지 세어주는 함수이다. 이 함수에서 리턴되는 값으로 i가 올바른 h인지 판단할 예정이다.

 

 두번째 조건인 '나머지 논문이 h번 이하로 인용되었을때'를 만족하는지 판단하기 위해 down_paper라는 함수를 만들었다.

 

down_paper 함수는 citation 배열과 up_paper가 리턴한 cnt_up를 전달받아 citations 내에 cnt_up보다 작은 paper가 몇개인지 세어준다.

 

down_paper가 리턴한 값이 up_paper 이하가 맞다면 i는 올바른 h 가 된다.

 

반복문이 paper의 개수만큼 돌아가므로 모든 경우의 수를 탐색할 수 있다.

3. 코드

나의 풀이:

def up_paper(citations, answer):
    cnt = 0
    for cit in citations:
        if cit >= answer:
            cnt += 1
    return cnt

def down_paper(citations, answer):
    cnt = 0
    for cit in citations:
        if cit < answer:
            cnt += 1
    return cnt

def solution(citations):
    for i in range (len(citations)+1):
        if up_paper(citations, i) >= i:
            cnt_up = up_paper(citations, i)
            if down_paper(citations, cnt_up) <= cnt_up:
                cnt_final = up_paper(citations, cnt_up)
    return cnt_final

 

효율적인 풀이(파라메트릭 서치):

def solution(citations):
    hIdx = 0
    citations.sort()
    left, right = 0, len(citations) - 1
    while left <= right:
        mid = (left + right) // 2
        if citations[mid] >= len(citations) - mid:
            hIdx = max(hIdx, len(citations) - mid)
            right = mid - 1
        else:
            left = mid + 1
    return hIdx

 

간단한 풀이:

def solution(citations):
    citations.sort(reverse=True)
    for idx , citation in enumerate(citations):
        if idx >= citation:
            return idx
    return len(citations)