H-Index

🔒 문제

🧠 생각의 흐름

문제를 읽자마자 "뭐야 너무 쉬운데?"
"일단 내림차순해서 큰 인용수를 갖는애들을 순서대로 검사하면서 갯수를 만족(갯수 >= 논문 인용수) 하는 애를 만나면 바로 break 하면 되잖아?"
라는 생각이 직관적으로 떠올랐다.

그리고 보기좋게 틀렸다.

🟥 실수

큰 피 인용수를 갖는 논문 원소를 하나하나 검사한다는 접근은 맞는데
위의 생각 흐름대로 코드를 짜면 다음과 같은 코드가 나온다.

 fun solution(citations: IntArray): Int {
     var hIndex : Int = 0
     citations.sortDescending()
     for ((index, citation) in citations.withIndex()) {
         if (citation > 1000) continue
         if (index + 1 >= citation) {
             hIndex = index + 1
             break
         }
     }
     return hIndex
  }

⚠️ H-Index는 실제 원소 값이 아닐 수 있다.

예를 들면 다음과 같은 케이스이다.

[4, 0, 6, 1, 5]

(1) 내림차순 정렬 후
[6, 5, 4, 1, 0]

(2) 검사 순서
6-> 5-> 4 -> 1-> 0

(3) 4를 검사하고 1로 넘어갈 때 반례가 발생한다.
그림으로 표현하면 다음과 같다.

6, 5, 4까지 검사했을 때 인용 수가 3 이상인 논문이 3개 (6, 5, 4) 존재하므로 답은 3이지만
이 식으로 진행하면 4다음에 1을 H-Index로 검사하기 때문에 1을 반환한다.

알고리즘 정리

(1) 인용 횟수에 따라 내림차순 한다.
(2) 인용 수가 1000을 넘는 것은 H-Index 가 될 수 없으므로 제외한다.
(3) 모든 논문의 인용수가 1000을 넘을 경우 전체 논문 수가 H-Index이다.
(4) 정렬된 논문 배열을 인용수가 큰 논문부터 검사한다.

[조건식] : loop 에서 현재까지 논문 갯수 (index 번호 + 1)가 지금 논문 인용수와 다음 논문 인용수 (다음으로 작은) 범위 내에 존재하는가?
true -> return H-Index
false -> continue

🔑 풀이

class HIndex {
    fun solution(citations: IntArray): Int {
        var hIndex : Int = 0
        citations.sortDescending()

        // citations 내의 원소가 모두 size 보다 큰경우 (ex. 1001 짜리가 100개 있으면 답은 100)
        if (citations.last() > citations.size) return citations.size
        
        for ((index, citation) in citations.withIndex()) {
            if (citation > 1000) continue
            if (index + 1 == citations.size) break // handling index out of bound

            val nextCitation = citations[index + 1]

            // [nextCitation ~ citation] 범위 내에 갯수를 가리키는 값이 존재하는가?
            if (IntRange(nextCitation, citation).contains(index + 1)) {
                hIndex = index + 1
                break
            }
        }

        return hIndex
    }
}

---

🛠️ 풀이 개선

class Solution {
    fun solution(citations: IntArray): Int {
        citations.sortDescending()

        for ((index, citation) in citations.withIndex()) {
            if (citation < index + 1) return index
        }
       
        return citations.size
    }
}