[프로그래머스/JS] - 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값이 반드시 배열 안에 존재하는 인용 횟수 값 중 하나일 필요는 없다는 것입니다. (예: [100, 100, 100]의 H-Index는 100이 아니라 3입니다.)

 

해결 방법: 내림차순 정렬 후 순차 비교

이 문제의 핵심은 모든 숫자를 하나씩 비교하는 완전 탐색 방식 대신, 내림차순 정렬을 통해 조건 확인을 단순화하는 것입니다.

1. 내림차순 정렬 (sort): citations 배열을 가장 많이 인용된 논문부터 순서대로 내림차순 정렬합니다. ([6, 5, 3, 1, 0])
2. 순위와 인용 횟수 비교: 배열을 0번 인덱스부터 순회하면서, "현재까지 센 논문의 개수(순위)"와 "해당 논문의 인용 횟수"를 비교합니다.
   • 1등 논문(6회 인용) ≥ 1편 -> 조건 만족 (H-Index = 1)
   • 2등 논문(5회 인용) ≥ 2편 -> 앞의 논문도 당연히 5회 이상이므로 조건 만족 (H-Index = 2)
   • 3등 논문(3회 인용) ≥ 3편 -> 조건 만족 (H-Index = 3)
   • 4등 논문(1회 인용) < 4편 -> 조건 불만족! 더 이상 탐색할 필요 없음
3. 효율성: 이렇게 정렬을 활용하면 배열을 한 번만 순회 O(N)하면 되므로, 반복문 안에서 filter를 돌리는 방식 O(N^2)보다 훨씬 빠르고 효율적으로 정답을 찾을 수 있습니다.

 

제출 코드

function solution(citations) {
    // 1. 인용 횟수를 내림차순(가장 큰 수부터)으로 정렬합니다.
    citations.sort((a, b) => b - a);
    
    let answer = 0;
    
    // 2. 앞에서부터 차례대로 확인합니다.
    for (let i = 0; i < citations.length; i++) {
        const count = i + 1; // 1편, 2편, 3편... (사람이 세는 논문의 누적 개수)
        const citation = citations[i]; // 해당 논문의 실제 인용 횟수
        
        // 3. 인용 횟수가 논문 개수보다 크거나 같다면 정답 갱신!
        if (citation >= count) {
            answer = count;
        } else {
            // 조건을 만족하지 못하는 순간이 오면 더 이상 볼 필요 없이 반복문 종료
            break; 
        }
    }
    
    return answer;
}