[프로그래머스 LV2] H-Index

---

내용을 제대로 이해하는 것이 어려웠던 문제였습니다. 저 뿐만 아니라 많은 사람들이 이 문제로 골치가 아팠던 것 같은데 제 나름대로 이해한 부분을 적어보려고 합니다.

문제

H-Index 링크

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.

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

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

제한사항

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

입출력 예

내 풀이

우선, H-Index는 h의 최댓값을 구하는 것이었기 때문에 저는 i를 큰 수부터 작은 수로 거꾸로 적용해가면서 조건이 맞을 때까지 확인했습니다. 예를 들어 아래와 같이 list가 있을 때, 처음에 i는 8이 됩니다. 즉, 8편 이상의 논문의 인용 수가 8 이상이어야 합니다. 이를 확인하는 방법은 인용 수가 많은 논문부터 8개의 논문을 뽑을 때, 가장 적은 인용 수의 논문을 확인하는 것입니다. list를 오름차순 정렬시켰을 때, 8편 중 가장 적은 논문 인용 수는 0입니다. 즉, $0 \not\ge 8$ 이므로 H-Index는 8이 될 수 없습니다. 같은 방식으로 H-Index는 7이 될 수 없습니다. 그렇게 i가 내려가다가 $i = 4$일 때, $6 \ge 4$가 성립하게 되고, H-Index는 4임을 알 수 있습니다! 즉, 이 문제는 인용 수가 많은 논문부터 [c - i]개의 논문을 뽑을 때, 가장 적은 인용 수가 i보다 크거나 같은 지를 확인하는 문제입니다.

따라서, 아래와 같은 코드를 작성할 수 있습니다.

def solution(citations):
    citations = sorted(citations)
    c = len(citations)
    for i in range(c, 0, -1) :     # 최댓값을 구하는 것이므로 큰수부터 거꾸로 적용
        if citations[c - i] >= i :     # 인용이 많은 논문부터 (c - i)개의 논문을 뽑을 때,
            return i                   # 가장 적은 인용수가 i보다 크거나 같아야 함.
    return 0

다른 사람들의 풀이

좋은 풀이가 두 개 있어서 둘 다 가져와 봤습니다. 우선 첫 번째 풀이는 제 코드와는 반대로 i를 작은 수부터 큰 수로 올라가면서 H-Index를 찾은 코드입니다. 저는 오히려 i를 작은 수부터 풀어내는 것이 이해가 어렵더라구요. 😅 문제에서 나머지 논문이 h번 이하 인용되었다는 문구가 있는데 이 부분을 이용해서 코드로 풀어낸 것 같습니다.

위의 풀이도 대단하다고 생각하는데 두 번째 풀이는 단 네 줄의 코드로 문제를 풀었습니다…😮😮😮 아래의 코드를 위의 굿노트 문제로 적용시켜 보았습니다. (0, 8편)에서 작은 수는 0, (1, 7편)에서 작은 수는 1, (3, 6편)에서 작은 수는 3, … (6, 4편)에서 작은 수는 4, … 이렇게 둘 중 작은 수를 뽑은 리스트를 만듭니다. -> [0, 1, 3, …, 4, …]. 그 다음 이 리스트 원소들 중 가장 큰 수가 H-Index가 된다는 내용인 것으로 보입니다. 4를 기준으로 오른쪽 원소들은 H-Index의 조건에 부합하지만, 최댓값이 아니므로 제외되고, 왼쪽 원소들은 H-Index 조건을 만족하지 않습니다. 따라서, 리스트의 max 값이 H-Index가 됩니다!

# 풀이 1
def solution(citations):
    citations = sorted(citations)
    c = len(citations)
    for i in range(c):
        if citations[i] >= c-i:
            return c-i
    return 0

# 풀이 2
def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer