[프로그래머스/JAVA] H-Index - 정렬

https://programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

 

H-Index라고 하는 것에 대한 정의가 실제로 존재했다!

위키백과에 말과 프로그래머스를 인용하자면

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

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

 

그러면서 다음과 같은 예시를 쥐어주었다.

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

 

즉 여기서 말하는 3은
3보다 큰 값이 3개 있으며, 3보다 작은 값은 2개이므로 모든 조건에 만족하므로 3이라는 것이다.
return값으로 4가 될 수 없는 이유는 조건대로라면 4번 이상 인용된 논문이 4편 이상되어야 한다는 말인데 4보다 큰 값은 2개 밖에 없기 때문에 조건을 충족할 수 없다.

우리가 알 수 있는 부분을 짚어보자.

먼저, return값의 가장 최소가 될 수 있는 수는 바로 배열 길이가 짝수일 때에는 길이 / 2 가 될 것이고, 길이가 홀수일 때에는 길이 / 2 + 1 이 될 것이다. h번 이상 인용된 것이 h편 이상이어야 하고, 나머지 논문이 h번 이하 인용되었기 때문에 return의 최솟값은 당연히 이렇게 될 수 밖에 없다.

그렇다면 최댓값은 무엇이 될까? 바로 배열의 길이이다.
예를 들어 [20, 21, 22, 23, 24] 라는 배열이 주어진다면 h는 5가 될 것이다. 모든 논문이 5와 같거나 높고, 이 외 나머지는 0회 인용되었기 때문에 조건이 성립한다. 그러면 최댓값부터 검사해보자.

최댓값이 배열의 길이라는 것을 알았기 때문에 위의 예시와 같이 [3, 0, 6, 1, 5] 에서 검사해보겠다.
먼저 정렬을 실시해준다. [0, 1, 3, 5, 6] 과 같은 배열이 될 수 있도록.
이제, 최댓값은 5이므로 5를 대입해보도록 하겠다. 

그런데 어떻게 알 수 있을까?

5라고 하는 것은 모든 숫자가 5 이상이어야 한다. 즉, 최솟값이 5보다 크다는 것은 모든 값이 5보다 큰 것이므로 배열의 첫 번째 요소랑 비교하면 되겠다(정렬을 끝냈으니). 그런데 조건이 성립하지 않는다.

따라서 5는 아니라는 것이고, 그 보다 작은 숫자인 4를 집어 넣어보자. 4를 대입하면 전체 편 수에서 4개만 4이상이면 된다. 그럼 이제는 두 번째 요소에 접근하여 4보다 큰지 확인하도록 한다. 첫 번째 요소에 접근하지 않는 이유는 전체에서 4개만 입증되기만 하면 되기 때문이다. 4개만 입증되어도 h가 나오기 때문에 4개를 입증하기 위해서는 그 관문인 두 번째 요소를 파악하는 것이다.

이와 같은 방식으로 계속 이어나가게 된다면 언젠가 그 값을 찾을 수 있으리라 생각하지만, 그렇게 값이 나오게 되지 않을 경우를 대비하여 index값이 배열을 벗어나게 된다면 0을 return할 수 있도록 고려했다.

문제 해법

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int max = citations.length;
        int index = 0;
        while(citations.length > index) {
            if(max <= citations[index])
                return max;
            max--;
            index++;
        }
        return 0;
    }
}