프로그래머스 42747 - H-Index (Lv.2)

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

// 프로그래머스 42747 - H-Index (Lv.2)
// https://school.programmers.co.kr/learn/courses/30/lessons/42747

// 문제 설명
// 논문 n편의 인용 횟수 배열 citations가 주어진다.
// "h번 이상 인용된 논문이 h편 이상"을 만족하는 h의 최댓값(H-Index)을 반환하라.

// 제약 조건
// 1 <= 논문 수 <= 1,000
// 0 <= 인용 횟수 <= 10,000

// Example
// Input : citations = [3, 0, 6, 1, 5]
// Output: 3
//   3번 이상 인용된 논문이 3편(3, 6, 5)이고, 4편 이상은 안 되므로 h = 3

// 접근 — 내림차순 정렬 후 경계 찾기
// 1) 인용 수를 내림차순으로 정렬한다.
// 2) 앞에서부터 h번째(0-based h) 논문을 보면, 그보다 앞의 논문들은 전부 그 이상 인용됐다.
//    따라서 citations[h] >= h+1 이면 "h+1번 이상 인용된 논문이 h+1편 이상"이 성립.
// 3) 조건이 깨질 때까지 h를 늘리면 마지막 h가 답이다.
// 시간 O(n log n), 공간 O(1)

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>()); // 내림차순 정렬

    int h = 0;
    while (h < (int)citations.size() && citations[h] >= h + 1)
        h++;                                  // h+1번째 논문도 h+1회 이상 인용됐으면 h 확장
    return h;
}

정리

• 정의(“h번 이상 인용된 논문이 h편 이상”)를 그대로 검사하려면 h 후보마다 배열을 다시 세야 한다. 내림차순 정렬이 이 검사를 인덱스 비교 하나로 바꾼다: 정렬 후 citations[h] >= h+1이면 앞쪽 h+1편은 전부 h+1회 이상 인용된 것이므로 h+1이 유효하다.
• 답은 조건이 성립하다가 깨지는 경계다. h=0부터 올라가며 처음 깨지는 지점에서 멈추면 그때의 h가 최댓값이다. 배열 끝까지 안 깨지면 논문 수 전체가 답이 되는데, h < size 조건이 그 경우를 자연스럽게 처리한다.
• 모든 인용이 0이면 첫 비교 citations[0] >= 1부터 실패해 h=0을 반환한다. h는 논문 수보다 클 수 없고 0일 수도 있다는 정의의 양 끝을 코드가 분기 없이 커버하는지 확인할 것.
• greater<int>() 대신 오름차순으로 정렬하고 뒤에서부터 세는 방법도 같은 복잡도지만, 인덱스 계산(n - h)이 하나 끼어들어 실수하기 쉽다. 정의가 “많이 인용된 것부터”이니 내림차순이 정의와 코드가 일치해 읽기 편하다.
• 검증: 예제 [3,0,6,1,5] → 3, 추가로 [0,0,0] → 0, [10,8,5,4,3] → 4 통과(MSVC /std:c++17 컴파일·실행).