274. H-Index (LeetCode)

문제 링크 → LeetCode 274. H-Index

---

문제 설명

과학자가 발표한 논문 N편의 인용 횟수가 담긴 citations 배열이 주어집니다. H-Index는 h번 이상 인용된 논문이 h편 이상이고, 나머지는 h번 이하 인용된 경우의 최대 h 값.

예시

Input: citations = [3, 0, 6, 1, 5]
Output: 3
// 3번 이상 인용된 논문이 3편 → [3, 6, 5]
// 나머지는 3번 이하 → [0, 1]

Input: citations = [100]
Output: 1
// 1편이 1번 이상 인용 → H = 1

아이디어

가능한 h 값 중 가장 큰 값을 찾는 문제.

방법 1: 정렬 + 선형 탐색

• 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는 불가능

---

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

핵심 아이디어

• citations[i] 값이 크더라도 H-Index는 최대 n까지만 가능
• 0 ~ n까지의 버킷 배열을 만들어 인용 횟수별 논문 수를 카운팅
• 뒤에서부터 누적합으로 i번 이상 인용된 논문이 i편 이상인 시점을 찾음

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
    } else {
      count[c] += 1
    }
  }

  let total = 0
  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