문제 이해

입력

• 정수 배열 citations
• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

출력

• 정수 h-index

요구 사항

• h-index → 적어도 h편 이상의 논문이 h회 이상 인용
• h-index 최대값

문제 풀이

1. 역순 정렬 후, 배열 순회 1O(nlogn)

   • 역순으로 정렬
   • for 루프를 돌면서, citations[i] < i+1인 i를 리턴
     • 루프를 돌면, 인용 횟수는 감소하고 논문 개수는 증가함
       • 그래프 그려 보면 됨.
     • 따라서, 위 조건이 만족할 때 i가 h의 최대값
   • 없을 경우, len(citations) 리턴

2. 역순 정렬 후, 배열 순회 2O(nlogn)

   • 역순으로 정렬
   • min(i + 1, citations[i]) → 현재 루프에서 h-index
   • max 값을 갱신

3. 계수 정렬 O(n)

   • n편의 논문이 있다면, 최대 h-index는 n
   • 인용 횟수에 따라 논문을 카운팅하고, 뒤에서 부터 누적합
   • total ≥ i인 경우 i 리턴