문제 25 - H-Index (Python)

프로그래머스

H-Index는 h번 이상 인용된 논문이 h편 이상이 되는 h의 최댓값을 찾는 문제입니다. 핵심은 인용 횟수를 정렬한 뒤, 가능한 h 값을 논문의 개수 기준으로 줄여가며 검사하는 것입니다.

---

1.  나의 풀이

 

def solution(citations):
    citations = sorted(citations, reverse=True)
    h_index = len(citations)

    while h_index > 0:
        if citations[h_index - 1] >= h_index:
            break
        h_index -= 1

    return h_index

 

인용 횟수를 내림차순으로 정렬합니다.

citations = sorted(citations, reverse=True)

 

예를 들어 입력이 다음과 같다면,

[3, 0, 6, 1, 5]

 

정렬 결과는 다음과 같습니다.

[6, 5, 3, 1, 0]

 

내림차순으로 정렬하면 앞쪽에 있는 논문일수록 인용 횟수가 많습니다. 따라서 h_index번째 논문의 인용 횟수가 h_index 이상이면, 그 앞의 논문들도 모두 h_index 이상 인용되었다고 판단할 수 있습니다.

if citations[h_index - 1] >= h_index:

 

h_index = 5부터 시작해서 가능한 가장 큰 H-Index를 먼저 검사합니다. 조건을 만족하지 못하면 하나씩 줄입니다.

h_index -= 1

 

예제에서는 다음 순서로 검사합니다.

citations = [6, 5, 3, 1, 0]

h = 5 → citations[4] = 0 >= 5 거짓
h = 4 → citations[3] = 1 >= 4 거짓
h = 3 → citations[2] = 3 >= 3 참

 

따라서 정답은 3입니다.

---

2.  오늘 배운 점 및 복기 노트

H-Index는 배열 안의 값을 그대로 고르는 문제가 아님

입출력 예제에서는 정답이 3이고 배열 안에도 3이 있어서, 배열 내부의 특정 값을 찾는 문제처럼 보일 수 있습니다. 하지만 H-Index는 인용 횟수 자체가 아니라 조건을 만족하는 h의 최댓값입니다.

예를 들어 다음 경우를 보면 더 분명합니다.

[50, 50, 50]

 

이 경우 H-Index는 50이 아니라 3입니다. 논문이 3편뿐이므로, 3번 이상 인용된 논문이 3편 있다는 조건까지만 만족할 수 있습니다.

정렬을 통해 개수 세기를 줄일 수 있음

정렬하지 않으면 어떤 h에 대해 h번 이상 인용된 논문이 몇 편인지 매번 세어야 합니다. 하지만 내림차순 정렬을 하면, 특정 위치의 값만 보고도 그 앞의 논문들이 모두 그 이상 인용되었다는 사실을 알 수 있습니다.

[6, 5, 3, 1, 0]

 

여기서 세 번째 값이 3 이상이면, 앞의 세 논문은 모두 3 이상 인용된 논문입니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

오름차순 풀이

교재에서는 오름차순 정렬 풀이를 먼저 소개합니다.

def solution(citations):
    citations.sort()

    for idx, citation in enumerate(citations):
        if citation >= len(citations) - idx:
            return len(citations) - idx

    return 0

 

오름차순으로 정렬하면 현재 위치 오른쪽에 있는 논문들은 모두 현재 논문보다 인용 횟수가 크거나 같습니다.

[0, 1, 3, 5, 6]

 

현재 위치가 idx일 때, 오른쪽에 남은 논문 수는 다음과 같습니다.

 

len(citations) - idx

 

따라서 현재 인용 횟수 citation이 남은 논문 수 이상이면 H-Index 조건을 만족합니다.

내림차순 풀이

교재의 내림차순 풀이는 다음과 같습니다.

 

def solution(citations):
    citations.sort(reverse=True)

    for idx, citation in enumerate(citations):
        if idx >= citation:
            return idx

    return len(citations)

 

내림차순에서는 앞에서부터 논문 개수를 늘려가며 봅니다.

[6, 5, 3, 1, 0]

 

idx가 citation 이상이 되는 순간, 더 이상 H-Index를 키울 수 없습니다. 그래서 그 시점의 idx가 가능한 최대 H-Index가 됩니다.

나의 풀이와 교재 풀이의 차이

교재의 내림차순 풀이는 앞에서부터 증가하면서 실패 지점을 찾습니다. 나의 풀이는 반대로 가능한 최댓값부터 시작해서 성공 지점을 찾습니다.

교재 풀이: 작은 h부터 늘려가다가 실패 지점 반환
나의 풀이: 큰 h부터 줄여가다가 성공 지점 반환

 

두 방식 모두 정렬을 이용해 h번 이상 인용된 논문이 h편 이상인지를 빠르게 판단한다는 점은 같습니다.