274. H-Index (LeetCode)

🔗 문제 링크 → LeetCode 274. H-Index

---

🧩 문제 설명

과학자가 발표한 논문 N편의 인용 횟수가 담긴 citations 배열이 주어집니다.
H-Index는 다음과 같이 정의됩니다:

"h는 과학자의 논문 중에 h번 이상 인용된 논문이 h편 이상이고, 나머지는 h번 이하 인용된 논문일 때 가능한 값 중 최댓값이다."

citations 배열이 주어졌을 때, 가능한 가장 높은 H-Index 값을 구하세요.

예시

Input: citations = [3, 0, 6, 1, 5]
Output: 3
// 3번 이상 인용된 논문이 3편 있음 → [3, 6, 5]
// 나머지는 3번 이하 → [0, 1]
// 조건 만족하므로 H-Index = 3

Input: citations = [100]
Output: 1
// 1편의 논문이 1번 이상 인용됨 → H = 1 가능
// 그보다 큰 H는 논문 수가 부족해 불가능 → H-Index = 1

💡 아이디어

이 문제는 가능한 h 값들 중 가장 큰 값을 찾는 최적화 문제입니다.
정렬 후 조건을 만족하는 최대 h를 구하면 됩니다.

✅ 방법: 정렬 + 선형 탐색

• citations를 내림차순 정렬
• 정렬된 배열에서 citations[i] >= i + 1을 만족하는 최대 인덱스를 찾아 i + 1을 반환

function hIndex(citations: number[]): number {
  citations.sort((a, b) => b - a)

  for (let i = 0; i < citations.length; i++) {
    if (citations[i] < i + 1) {
      return i
    }
  }

  return citations.length
}

🛠️ 코드 동작 원리

1. 인용 수를 내림차순 정렬하여, 높은 인용 수부터 차례로 비교
2. i번째 논문이 i+1번 이상 인용되지 않았다면, 그게 한계
3. 그렇지 않으면 계속 탐색, 끝까지 도달하면 전체 논문 수가 H-Index

📊 시간 복잡도 & 공간 복잡도 분석

방식	시간 복잡도	공간 복잡도
정렬 + 탐색	O(n log n)	O(1)

🔄 다른 풀이 방법과 비교

• 카운팅 배열을 사용하는 O(n) 풀이도 가능하지만, 정렬 방식이 간단하고 직관적
• 큰 입력에서 시간 최적화를 원할 경우 Counting Sort 방식이 유리할 수 있음

📝 핵심 내용 요약

• 핵심 조건: h번 이상 인용된 논문이 h편 이상
• 최대의 h를 찾아야 함 → 내림차순 정렬 후 인덱스 비교
• 인용 횟수가 높더라도 논문 수가 적으면 높은 H-Index는 불가능
• 직관적이고 구현이 쉬운 정렬 방식이 가장 많이 쓰임

---

⚡ 방법: Counting (버킷) 방식 – O(n)

💡 핵심 아이디어

• citations[i] 값이 클 수 있으나, 논문 수 n을 넘는 인용은 결과에 영향 없음
  → 왜냐하면, H-Index는 최대 n까지밖에 될 수 없음
• 따라서 0 ~ n까지의 버킷(bucket) 배열을 만들어, 인용 횟수 별 논문 수를 카운팅
• 누적해서 i번 이상 인용된 논문이 i편 이상인 시점을 찾으면 그것이 H-Index

✅ TypeScript 코드

function hIndex(citations: number[]): number {
  const n = citations.length
  const count = new Array(n + 1).fill(0)

  // 버킷에 인용 수 별로 카운팅
  for (const c of citations) {
    if (c >= n) {
      count[n] += 1 // n 이상은 전부 n 버킷에 넣음
    } else {
      count[c] += 1
    }
  }

  let total = 0
  // 뒤에서부터 누적합 → h-index를 찾기
  for (let i = n; i >= 0; i--) {
    total += count[i]
    if (total >= i) {
      return i
    }
  }

  return 0
}

🛠️ 동작 방식 요약

1. citations의 모든 값에 대해 버킷을 채움 (O(n))
2. 큰 값부터 누적해서 total >= i인 지점을 찾으면 H-index (O(n))

📊 시간 복잡도 & 공간 복잡도

항목	복잡도
시간 복잡도	O(n)
공간 복잡도	O(n) (버킷 배열)

🔁 예시 설명

Input: citations = [3, 0, 6, 1, 5]
// n = 5 → 버킷 = [0, 0, 0, 0, 0, 0]

// count 배열:
// 0 → 1편
// 1 → 1편
// 3 → 1편
// 5 이상 → 2편 (5, 6 → count[5] += 2)

// count = [1, 1, 0, 1, 0, 2]

// 뒤에서부터 누적합 total 계산
i=5 → total=2  → total < i
i=4 → total=2  → total < i
i=3 → total=3  → total ≥ i → ✅ 정답: 3