[LeetCode 274] H-Index - 연구 논문의 영향력 측정 (탐욕법 + 정렬)

[LeetCode] H-Index - 연구 논문의 영향력 측정 (탐욕법 + 정렬)

문제 설명

LeetCode의 "H-Index" 문제는 연구자가 발표한 논문들의 인용 횟수를 분석하여 H-Index를 계산하는 문제입니다.

• 연구자가 발표한 논문의 인용 횟수가 배열 citations로 주어집니다.
• 연구자의 H-Index는 h 편의 논문이 최소 h번 이상 인용되었으며, 나머지 논문은 h번 이하로 인용된 경우의 최대값입니다.
• 항상 H-Index를 계산할 수 있다고 가정합니다.

---

📌 문제를 풀면서 생각한 과정

처음에는 각 논문의 인용 횟수를 순차적으로 확인하며 H-Index를 계산하는 방법을 떠올렸습니다.
하지만 효율적인 탐색이 필요하여 탐욕법(Greedy Algorithm)과 정렬을 활용한 최적화 방법을 도출했습니다.

---

📌 H-Index 계산 방법

✅ 핵심 아이디어

1. 논문을 인용 횟수 기준으로 내림차순 정렬합니다.
2. 각 논문이 i+1번째로 많이 인용된 논문인지 확인합니다.
   • citations[i] >= i + 1 → H-Index 가능
   • 더 이상 만족하지 않으면 마지막으로 i가 유효한 값이 됨

---

📌 탐욕법(Greedy) 코드

export function hIndex(citations: number[]): number {
  citations.sort((a, b) => b - a); // 내림차순 정렬

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

  return h;
}

---

📌 실행 예제 분석

console.log(hIndex([3, 0, 6, 1, 5])); // Output: 3
console.log(hIndex([1, 3, 1]));       // Output: 1
console.log(hIndex([10, 8, 5, 4, 3])); // Output: 4
console.log(hIndex([0, 0, 0, 0]));     // Output: 0
console.log(hIndex([100]));            // Output: 1

✅ 논문을 내림차순으로 정렬하여 탐색을 최적화 ✅ 각 논문이 i+1번째 이상 인용되었는지 확인 ✅ H-Index가 더 이상 증가하지 않으면 중단

---

📌 시간 및 공간 복잡도 비교

방법 시간 복잡도 공간 복잡도 특징

정렬 후 탐욕법(Greedy)

O(N log N)

O(1)

최적의 방법, 빠름

✅ 탐욕법(Greedy)과 정렬을 활용하여 최적의 해결법을 적용 🚀

---

📌 Jest 테스트 코드

describe("Medium 274: H-Index", () => {
  it("returns the correct H-Index for a standard case", () => {
    expect(hIndex([3, 0, 6, 1, 5])).toEqual(3);
  });

  it("returns the correct H-Index when values are small", () => {
    expect(hIndex([1, 3, 1])).toEqual(1);
  });

  it("returns the correct H-Index when all values are high", () => {
    expect(hIndex([10, 8, 5, 4, 3])).toEqual(4);
  });

  it("returns 0 when all citations are 0", () => {
    expect(hIndex([0, 0, 0, 0])).toEqual(0);
  });

  it("returns 1 when there is only one highly cited paper", () => {
    expect(hIndex([100])).toEqual(1);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (단일 요소, 정렬된 점프, 초기 정지 상황)

---

📌 최종 정리

• 탐욕법(Greedy)과 정렬을 활용하여 O(N log N) 최적화 적용
• "현재 논문의 인용 횟수가 i+1개 이상인지"를 확인하여 H-Index를 계산
• 추가 배열 없이 O(1) 공간복잡도로 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법 + 정렬"을 우선 고려해 보세요! 🚀