Java] 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회 이하입니다.

입출력 예

citationsreturn

[3, 0, 6, 1, 5]

3

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

※ 공지 - 2019년 2월 28일 테스트 케이스가 추가되었습니다.

---

1. https://en.wikipedia.org/wiki/H-index "위키백과"
2. https://www.ibric.org/myboard/read.php?Board=news&id=270333
   
   

문제 설명

지문만 보고는 구하는 공식을 오해하기 쉽다. 나뿐만 아니라, 다른 사람들도 마찬가지로 지문과 예시에 관해서 불만을 가진 사람들이 많으니 지문도 중요하겠지만, 참조된 위키백과 또는 뉴스 기사를 추가적으로 참조하기를 바란다.

 

우선, 내가 처음 이해한 방식은 다음과 같다.(잘못된 방식)

"citations 안에 존재하는 변수들 중에 하나를 h로 잡고, h 이상의 값을 가진 수가 h개 이상이고, h 이하의 값을 가진 수가 h개 이하인 수 중 가장 큰 값을 구하라"라고 이해하고 풀었지만, 위 내용대로 코드를 구현하고 아무리 수정해도 체 점했을 때 점수가 터무니없이 나와 뭔가 문제가 있다고 생각했다.

 

H-index에 관한 관련 자료들을 살펴봤을 때, 다음과 같은 결론을 내렸다(올바른 방식)

"0 ~ citations.length까지의 값 중 하나를 h로 잡고, citations 배열 내부에서 h 이상인 값이 h개 이상이어야 한다"

위 방식은 h-index를 구하는 100% 올바른 답은 아니며, 오로지 이 문제를 풀기 위해 알아야 할 것들만 요약하였고, 더 자세히 이해하기 위해서는 위키백과 또는 뉴스 기사를 참조하기를 바란다.

 

해당 결론을 적용시켰을 때, 정답이 될 수 있는(h 변수의 후보가 될 수 있는) 최댓값은 citations.length다. h 이상인 값이 h개 이상이어야 하는데, 최대 길이를 넘는데 h개 이상은 될 수 없으니 말이다.

예를 들어, {9, 11, 12, 13, 14}가 있는데 9를 h로 잡았을 때, 뒤에 있는 변수들의 값이 어떻든 간에 총길이가 5이니 9 이상인 수가 9개 이상이 될 수는 없다.

 

그리고 최댓값을 구하기 위해서는 h의 시작을 citations.length에서 시작하여 하나씩 줄여 나가고, 조건에 부합하는 h를 찾았을 때 바로 반환하면 된다.

 

시간 복잡도가 더 중요한 문제였다면, 정렬을 한 뒤에 h보다 큰 값을 찾았을 때 if(전체 길이 - 현재 인덱스) 등의 추가적인 연산을 했을 텐데, 그렇게까지 하지 않아도 통과가 되니 해당 부분은 구현하지 않았다.

 

그럼, 위 방식을 적용한 내용으로 해법을 설명드립니다.

해법

1. citations.length에서 하나씩 줄여가며 for문을 만들고, 현재의 값을 h라 가정한다(i를 h로 가정)

2. citations 배열 전체를 반복문을 돌리며, h 이상인 값이 존재한다면 higher 변수를 증가시키며 개수를 카운팅 한다.

3. h 이상인 값이 h개 이상인지 확인하며, 맞다면 해당 값을 반환한다.

코드

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int higher = 0;

        for (int i = citations.length; i >= 0; i--) {
            higher = 0;
            for (int j = 0; j < citations.length; j++) {
                if (i <= citations[j]) {
                    higher++;
                }
            }
            if (higher >= i) {
                return i;
            }
        }

        return 0;
    }
}

 

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

코딩테스트 연습 - H-Index