H-Index

[hsskey]

문제 설명 | H-Index

연구자의 논문 인용 수 배열 citations가 주어질 때, H-Index를 구하는 문제

H-Index 정의:

• 연구자가 발표한 논문 중 h 편 이상이 h회 이상 인용되었을 때, 가능한 h 값 중 최대값을 구한다.

---

📝 제약조건

• 1 <= citations.length <= 5000 (논문의 개수)
• 0 <= citations[i] <= 1000 (각 논문의 인용 횟수)

---

💡 예시

Example 1

Input:

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

Output:

3

Explanation:

• 논문 인용 횟수: [3, 0, 6, 1, 5]
• 정렬 후: [6, 5, 3, 1, 0]
• h = 3일 때, 3편 이상이 3회 이상 인용됨 → 최대 h-index는 3

---

🚀 문제 해결 과정

Step 1: 문제 이해하기

작은 예시로 직접 계산해보기

논문 개수	인용 횟수 배열	h-index 계산
1개	[5]	1
2개	[4, 5]	2
3개	[10, 8, 5]	3

• 논문의 개수가 h편 이상이고, 각 논문이 h번 이상 인용되었을 때의 h 중 최대값을 찾아야 한다.

---

Step 2: 접근 방법

💡 직관적인 접근법 (완전탐색)

• 모든 h에 대해 논문 개수를 세고 조건을 만족하는 h 중 최댓값 찾기 → O(n²) (비효율적)

💡 정렬을 활용한 방법 (O(n log n))

1. 내림차순 정렬 → 인용 횟수가 큰 순서대로 정렬
2. 왼쪽에서부터 탐색하면서 h-index 찾기
   • 현재 i + 1개의 논문이 citations[i] 이상 인용되었는지 확인
   • 조건이 깨지는 순간, 최대 h를 반환

---

Step 3: 코드 설계

1. citations 배열을 내림차순 정렬
2. for 문을 돌면서 i + 1번째 논문의 인용 횟수와 비교
3. 조건을 만족하는 최대 h-index를 result에 저장
4. 조건이 깨지는 순간 result 반환

---

Step 4: 코드 구현

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    // 1. 내림차순 정렬
    citations.sort((a, b) => b - a);

    let result = 0;

    // 2. 정렬된 상태에서 h-index 찾기
    for (let i = 0; i < citations.length; i++) {
        if (citations[i] >= i + 1) {
            result = i + 1;
        } else {
            break;  // 조건이 깨지면 중단
        }
    }

    return result;
};

[hsskey]

다른풀이

Step 2: 접근 방법

💡 직관적인 접근법 (완전탐색)

• 모든 h에 대해 논문 개수를 세고 조건을 만족하는 h 중 최댓값 찾기 → O(n²) (비효율적)

💡 정렬을 활용한 방법 (O(n log n))

1. 내림차순 정렬 → 인용 횟수가 큰 순서대로 정렬
2. 왼쪽에서부터 탐색하면서 h-index 찾기
   • 현재 i + 1개의 논문이 citations[i] 이상 인용되었는지 확인
   • 조건이 깨지는 순간, 최대 h를 반환

💡 더 빠른 방법 (카운팅 배열 활용, O(n))

1. H-index의 가능한 최대값은 n을 넘을 수 없음.

   • 따라서 인용 횟수별 논문 개수를 저장하는 배열(count)를 사용하면 정렬 없이도 계산 가능!

2. 인용 횟수별로 논문의 개수를 저장할 count 배열을 만든다.

   • count[i] → "인용 횟수가 i인 논문의 개수"
   • 단, i > n인 경우 count[n]에 모두 저장 (최대 h-index는 n이므로)

3. 큰 인용 횟수부터 논문 개수를 누적하며 h-index를 찾는다.

   • totalPapers 변수를 사용해 현재까지 누적된 논문 개수를 저장
   • totalPapers >= h 를 만족하는 최대 h를 찾으면 종료

---

Step 3: 코드 설계

1. citations 배열을 순회하며 인용 횟수를 카운트 (count 배열 사용)
2. 큰 인용 횟수부터 탐색하며 h-index 계산
   • 현재 h에서 totalPapers가 h 이상이면 h-index 반환
   • 조건이 깨지면 종료

---

Step 4: 코드 구현

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    let n = citations.length;
    let count = new Array(n + 1).fill(0); // 인용 횟수별 논문 개수 저장
    
    // 1️⃣ 인용 횟수를 카운팅
    for (let c of citations) {
        if (c >= n) {
            count[n]++;  // n번 이상 인용된 논문은 count[n]에 저장
        } else {
            count[c]++;  // 해당 인용 횟수 위치에 저장
        }
    }

    // 2️⃣ H-index 계산 (큰 값부터 누적)
    let totalPapers = 0;
    for (let h = n; h >= 0; h--) {
        totalPapers += count[h];  // 현재 h 이상 인용된 논문 개수 누적
        if (totalPapers >= h) {
            return h;  // 최대 h-index 찾으면 반환
        }
    }

    return 0;  // 기본적으로 h-index가 0일 수도 있음
};