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

• 출처: 프로그래머스 42747
• 분류: 정렬 · Lv.2

문제

논문별 인용 횟수 배열 citations가 주어진다. h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었을 때, h의 최댓값(H-Index)을 반환한다.

핵심

내림차순 정렬하면 i번째(0-based) 논문은 “인용수가 i+1번째로 높은 논문”이다. citations[i] >= i + 1이 성립하는 마지막 i에서 h = i + 1이다.

풀이

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<>());

    int h = 0;
    for (int i = 0; i < (int)citations.size(); i++) {
        if (citations[i] >= i + 1)
            h = i + 1;
        else
            break;
    }
    return h;
}

메모

• 내림차순 정렬 후 citations[i]는 상위 i+1번째 인용수다. citations[i] >= i + 1이면 “i+1편 이상이 i+1번 이상 인용됨”을 의미한다
• citations[i] < i + 1이면 그 이후도 전부 조건을 만족하지 않으므로 break할 수 있다
• (int)citations.size()로 캐스팅하는 이유: size()는 size_t(unsigned)를 반환하고, int i와 비교하면 signed/unsigned 비교 경고가 발생한다
• H-Index의 정의에서 “나머지 논문이 h번 이하”는 별도로 검증할 필요 없다. 내림차순 정렬 상태에서 citations[h]부터는 자동으로 h 이하다

복잡도

풀이	시간	공간
정렬 + 선형 탐색	O(N log N)	O(1)