정렬 - H-index

정렬 - H-index(programmers.co.kr/learn/courses/30/lessons/42747?language=kotlin)를 풀어봤다.

 

풀이는 아래와 같다.

 

    fun solution(citations: IntArray): Int {
        citations.sortedDescending().forEachIndexed { index, i ->
            if (index >= i) {
                return index
            }
        }

        return citations.size
    }

 

처음엔 문제가 이해가 안갔다... 최초 풀이는 아래와 같다

        var answer = 0

        for (i in citations.indices) {
            val h_index = citations[i]
            var upCount = 0
            var downCount = 0
            for (j in citations.indices) {
                if (h_index <= citations[j]) {
                    upCount ++
                } else {
                    downCount ++
                }
            }
            
            if (upCount == h_index && downCount <= h_index) {
                answer = h_index
                return answer
            }
        }

        return answer

왜 이렇게 생각했냐면, 예제인 {3, 0, 6, 1, 5} 를 5개의 논문을 각각 3번, 0번 6번, 1번, 5번 인용했고, 3번 이상 인용한 사람은 3개의 논문이며, 3번 이하 인용한 논문은 2개이다. 라고 생각했다.

하지만 이걸 토대로 돌리면 다 틀린다. 16번은 맞았다. 왤까....?

 

그래서 위키를 읽어봤다.

역시 영어는 어렵다. 구글링 했다...............

 

문제 이해부터 틀렸다. 문제는 "x번 인용한 논문이 x번 이상일 경우"를 생각하면 된다. 즉, 각 논문당 몇번을 이용하던, 몇번의 인용이 몇개인지가 중요하다. 예를 들어, [10, 100], 즉, 2개의 논문, 10번, 100번의 인용이 있다고 치자. 이것의 답은 무엇일까?

 

답인 h_index 는 10? 100? 아니다 2다.

 

왜 2일까? 생각해보면, 10번, 100번의 인용은 모두 2번이상을 인용했으며, 2개의 "이상"의 논문이다. 즉, h_index = 2가 된다.

 

그렇다면, [2, 2, 2]는? 생각해봐라.(답은 맨 밑에서...)

 

여튼 그렇다. 다시 계산을 했다. 내림차순으로 정렬해 [10, 100] 이라면 [100, 10]으로 바꾸기 위해 sortedsortedDescending() 을 사용했다. 또한, 위의 예제대로, 굳이 몇 번의 인용을 했느냐를 어레이에서 찾는게 아닌, 인덱스로 눈을 돌렸다. 이게 포인트다. "몇 번 이상"의 인용을 위해 index가 array 안에 담겨 있는 숫자보다 "크거나 같다면(=이상)" 해당 인덱스 이상을 이용한게 되므로, 바로 return해준다. 

 

여기서 끝이 아니다. index가 array에 담긴 수 이상임을 찾기 전에 for문이 끝이난다면, 어떻게 해야할까?

답은 해당 어레이의 크기를 리턴해주면 된다. 왜냐고? 논문의 갯수 이상을 인용할 수 없으니까!

 

 

 

 

 

 

 

답은 2다!

 

내가 사용한 예제는 다음과 같다.

        val citations00 = intArrayOf(3, 0, 6, 1, 5) 
        val citations01 = intArrayOf(10, 8, 5, 4, 3) 
        val citations02 = intArrayOf(4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6)
        val citations03 = intArrayOf(10, 50, 100)
        val citations04 = intArrayOf(2, 2, 2)
        val citations05 = intArrayOf(10, 100)
        println("3 = "+Level2_H_index(citations00))
        println("4 = "+Level2_H_index(citations01))
        println("6 = "+Level2_H_index(citations02))
        println("3 = "+Level2_H_index(citations03))
        println("2 = "+Level2_H_index(citations04))
        println("2 = "+Level2_H_index(citations05))