04/05 알고리즘 공부(86) - H-Index

조건

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한조건

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citations	returns
[3, 0, 6, 1, 5]	3

알고리즘 예상

1. citations을 groupBy로 인용 횟수로 묶는다.
2. map을 이용해 그룹화 된 배열을 key, value.count()로 묶는다.
3. 인용횟수로 내림차순 정렬을 한다.
4. 앞에서부터 차례로 count 변수에 it.value를 더하면서 count >= it.key를 비교한다.
5. 조건을 만족하면 break 하고 answer = count를 하고 반환한다.

 

초기 코드

class Solution {
    fun solution(citations: IntArray): Int {
        var answer = 0
        return answer
    }
}

 

내 코드

// 테스트 케이스 통과, 실패
class Solution {
    fun solution(citations: IntArray): Int {
        var answer = 0

        val citationsGroup = citations
            .groupBy { it }
            .map { (k, v) -> k to v.count() }
            .sortedByDescending { it.first }

        for (i in citationsGroup){
            answer += i.second
            if(answer >= i.first) break
        }

        return answer
    }
}

answer에 값을 더하는 과정이나 조건문 탈출하는 부분에서 오류가 생긴 듯하다.

// 성공
class Solution {
    fun solution(citations: IntArray): Int {
        var answer = 0

        val citationsGroup = citations
            .groupBy { it }
            .map { (k, v) -> k to v.count() }
            .sortedByDescending { it.first }

        for (i in citationsGroup){
            answer += i.second
            if(answer > i.first) {
                answer -= i.second
                break
            }
        }

        return answer
    }
}

탈출조건에서 등호를 빼고 탈출할 때 마지막으로 더한 값을 빼주는 연산을 추가했더니 통과했다.

다른 사람의 풀이

import kotlin.math.min

class Solution {
    fun solution(citations: IntArray) = citations.sortedDescending().mapIndexed { idx, item -> min(idx + 1, item) }.maxOf{it}
}

 

개선점 또는 배운점

1. 최대 원소 수 1000개, 최대 인용횟수 10000회라 계산할 것이 많아보여서 groupBy를 사용했는데 생각보다 계산 횟수가 적었다. 그룹화 하지 않고 단순히 내림차순으로 정렬해 n번째의 원소가 n+1번보다 많이 인용되었는지만 검사했다.