프로그래머스

프로그래머스 H-Index 풀이: 정렬 후 인용 수와 순위 비교

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

먼저 인용 횟수를 큰 순서로 정렬한 뒤, 앞에서부터 현재 순위와 인용 횟수를 비교하면 된다. 정렬 후 한 번만 확인하는 기본 흐름은 단순하지만, H-Index의 조건을 “순위 이상 인용된 논문 수”로 바꾸어 생각해야 하므로 Level 2로 판단했다. 별도의 복잡한 자료구조나 어려운 예외 처리는 필요하지 않다.

1. H-Index 문제

논문별 인용 횟수가 citations 배열로 주어질 때 연구자의 H-Index를 반환한다. H-Index는 다음 조건을 동시에 만족하는 가장 큰 정수 h다.

  • 인용 횟수가 h 이상인 논문이 h편 이상 있어야 한다.
  • 나머지 논문은 인용 횟수가 h 이하이어도 된다.

예를 들어 [3, 0, 6, 1, 5]를 내림차순으로 정렬하면 [6, 5, 3, 1, 0]다. 인용 횟수가 3 이상인 논문은 3편이고, 4 이상인 논문은 2편뿐이므로 H-Index는 3다.

중요한 조건은 다음과 같다.

  • citations의 길이는 1 이상 1,000 이하다.
  • 각 논문의 인용 횟수는 0 이상 10,000 이하다.
  • 인용 횟수가 많은 논문부터 정렬해도 H-Index의 크기만 계산하면 된다.
  • 인용 횟수가 0인 논문도 입력에 포함될 수 있다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

정렬 위치가 H-Index 경계가 되는 이유

인용 횟수를 내림차순으로 정렬하면 index번째 논문까지 앞에 index + 1편이 있다. 따라서 현재 위치에서 다음 조건을 확인하면 된다.

citations[index] >= index + 1

조건이 참이면 앞의 index + 1편이 모두 그만큼 이상 인용되었다. 처음 거짓이 되는 위치부터는 순위만 더 커지고 인용 횟수는 같거나 작아지므로 H-Index가 될 수 없다. 예를 들어 정렬 결과가 [6, 5, 3, 1, 0]이면 처음 세 위치는 조건을 만족하지만 네 번째에서 1 < 4가 된다. 따라서 H-Index는 3이다.

위치 index 인용 횟수 순위 index + 1 조건
0 6 1 통과
1 5 2 통과
2 3 3 통과
3 1 4 처음 실패

첫 위치부터 실패하면 H-Index는 0이다. 반대로 모든 위치가 통과하면 논문 수 전체가 H-Index가 된다. 이 경계가 코드에서 index를 반환하거나 끝까지 통과한 경우 길이를 반환하는 두 가지 결과에 대응한다.

오답 접근과 반례

배열에서 가장 큰 인용 횟수만 보고 H-Index로 정하면 안 된다.

citations = [100, 0, 0]

가장 큰 인용 횟수는 100이지만, 인용 횟수가 2 이상인 논문은 1편뿐이다. 따라서 H-Index는 100이 아니라 1이다. H-Index는 한 논문의 인용 횟수가 아니라, 같은 기준을 만족하는 논문 수가 기준 이상인지 함께 확인해야 한다.

반대로 정렬하지 않은 배열에서 단순히 앞의 값과 index + 1을 비교하면 큰 인용 횟수가 뒤에 있을 때 순위와 인용 횟수의 대응이 깨진다. 먼저 큰 값부터 정렬해야 한다.

시간·공간 복잡도

논문 수를 n이라고 하면 정렬에 O(n log n), 정렬된 배열을 한 번 확인하는 데 O(n)이 필요하다. 따라서 전체 시간 복잡도는 O(n log n)다.

입력 배열을 직접 정렬하고 인덱스와 결과만 사용하므로 알고리즘 관점의 추가 공간은 O(1)다. 다만 Python의 정렬 구현은 내부적으로 입력 크기에 비례하는 보조 메모리를 사용할 수 있다.

3. 문제 해결 코드 (Python)

citations를 내림차순으로 정렬하면 현재 위치 index에서 이미 index + 1편의 논문을 확인한 상태가 된다. 현재 인용 횟수가 그 순위보다 작아지는 첫 지점을 찾는다.

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

    for index, citation in enumerate(citations):
        rank = index + 1

        if citation < rank:
            return index

    return len(citations)

rank는 현재까지 포함한 논문 수다. citation < rank인 순간에는 rank편의 논문이 모두 rank번 이상 인용되었다고 볼 수 없으므로, 현재보다 큰 H-Index도 만들 수 없다. 함수는 입력 배열을 직접 정렬하므로 원본 순서를 보존해야 하는 상황이라면 citations[:]를 복사한 뒤 정렬해야 한다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 정렬 경계와 단일 논문 사례를 확인할 수 있다.

assert solution([3, 0, 6, 1, 5]) == 3
assert solution([0, 0, 0]) == 0
assert solution([10, 10, 10, 10]) == 4

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 0, 한 편, 모든 논문이 충분히 인용된 경우를 확인했다.

공식 예제

입력 기대 출력 확인 결과
citations = [3,0,6,1,5] 3 통과
citations = [1,2,3,4,5] 3 통과

추가 검증 1: 인용이 없는 논문만 있는 경우

입력: citations = [0, 0, 0, 0]
기대 출력: 0
확인 결과: 통과
검증 목적: 첫 번째 논문부터 조건을 만족하지 못하는 경계를 확인

추가 검증 2: 논문 한 편

입력: citations = [1]
기대 출력: 1
확인 결과: 통과
검증 목적: 최소 입력에서 한 논문이 한 번 인용된 경우 확인

추가 검증 3: 한 논문만 매우 많이 인용된 경우

입력: citations = [100, 0, 0]
기대 출력: 1
확인 결과: 통과
검증 목적: 가장 큰 인용 횟수 하나만으로 H-Index를 정하지 않는지 확인

추가 검증 4: 모든 논문이 충분히 인용된 경우

입력: citations = [10, 10, 10, 10]
기대 출력: 4
확인 결과: 통과
검증 목적: 끝까지 조건을 만족하면 논문 수 전체를 반환하는지 확인

5. 다른 풀이 방식 검색 및 비교

인용 횟수의 최댓값부터 가능한 H-Index를 하나씩 검사하는 방법도 생각할 수 있지만, 매번 논문을 다시 세면 불필요한 반복이 생긴다. 정렬 후 순위를 함께 확인하면 한 번의 순회로 조건이 처음 깨지는 위치를 찾을 수 있다.

인용 횟수의 범위가 작다면 빈도 배열을 만들어 정렬 없이도 계산할 수 있다. 하지만 이 문제에서는 입력 배열을 정렬하는 방식이 구현이 짧고, 현재 순위와 인용 횟수의 관계를 직접 보여준다는 장점이 있다.

마무리

H-Index는 가장 많이 인용된 논문 하나를 찾는 문제가 아니라, “최소 h번 이상 인용된 논문이 h편 이상 있는가”를 확인하는 문제다. 인용 횟수를 내림차순으로 정렬하면 현재 위치가 논문 수가 되므로, 인용 횟수가 현재 순위보다 작아지는 첫 지점을 찾으면 된다. 정렬과 한 번의 순회로 O(n log n) 시간에 H-Index를 계산할 수 있다.

관련 문제

#정렬#프로그래머스#난이도 2