[알고리즘] #H-Index

출처: https://programmers.co.kr/learn/courses/30/lessons/42747?language=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회 이하입니다.

 

입출력 예

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

 

입출력 예 설명

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

 

 

 

---

이번 문제는 사실 문제가 잘 이해가 되지 않고, 테스트 케이스가 1개 뿐이어서 어려웠다.

내가 잘못 생각했던 점은 두 가지가 있었는데

 

1. 'h번 이상 인용된 논문 갯수 = h번 이하 인용된 논문 갯수 = h' 라고 생각하고 문제를 풀음

2. 논문 갯수가 홀수개인 경우, 정답이 무조건 sorting된 정렬의 가운데 index라고 생각함

-> 만약 citations = [0, 15, 4, 0, 7, 10, 0]; 인 경우에는 틀리다.

 

그래서 이부분 때문에 초반에 문제를 푸는데 시간이 오래걸렸다.

 

import java.util.Arrays;
class Solution {
    public int solution(int[] citations) {
		// 정렬 
		Arrays.sort(citations);
		
		int h=citations[citations.length -1];
		while(h > -1) {
			// h보다 작은 숫자 갯수 = h 인지 
			if(isBiggerThanH(h, citations)) {
				return h;
			}
			
			h--;
		}
        return 0;
    }
	
	public boolean isBiggerThanH(int h, int[] arr) {
		int cnt = 0;
		for(int i=0; i<arr.length; i++) {
			if(arr[i] >= h) {
				cnt++;
			}
		}
		
		return h <= cnt;
	}
}

정확성 테스트

테스트 1 〉	통과 (13.19ms, 47.6MB)
테스트 2 〉	통과 (14.38ms, 48.2MB)
테스트 3 〉	통과 (14.28ms, 45.1MB)
테스트 4 〉	통과 (13.09ms, 48.3MB)
테스트 5 〉	통과 (13.81ms, 48.1MB)
테스트 6 〉	통과 (13.61ms, 47.5MB)
테스트 7 〉	통과 (11.36ms, 48.1MB)
테스트 8 〉	통과 (5.58ms, 44.9MB)
테스트 9 〉	통과 (8.34ms, 47.5MB)
테스트 10 〉	통과 (11.49ms, 48.3MB)
테스트 11 〉	통과 (14.73ms, 48.2MB)
테스트 12 〉	통과 (9.23ms, 45.4MB)
테스트 13 〉	통과 (14.30ms, 48.2MB)
테스트 14 〉	통과 (14.02ms, 47.8MB)
테스트 15 〉	통과 (15.20ms, 47.7MB)
테스트 16 〉	통과 (1.23ms, 44.6MB)

 

정확성 테스트는 모두 통과했지만, isBiggerThanH 메서드를 보면 array 크기 만큼 계속 비교를 하기 때문에 시간이 오래 걸린다.

 

 

---

#다른 사람들이 푼 풀이 방법

 

사실 이 방법에서 이해가 잘 가지 않는 부분은 citations.length-i 이다.

왜 저 값을 비교하는거지???ㅠㅠㅠㅠㅠ

 

i	max	min	citations[i]	citations.length - i
	0
4	1	1	6	1
3	2	2	5	2
2	3	3	3	3
1	3	1	1	4
0	3	0	0	5

이렇게 되어있는데 왜 citations.length-i를 비교하는지 잘 이해가 가지 않는다 ㅠㅠ

import java.util.Arrays;
class Solution {
    public int solution(int[] citations) {
		Arrays.sort(citations);

        int max = 0;
        for(int i = citations.length-1; i > -1; i--){
            int min = (int)Math.min(citations[i], citations.length - i);
            if(max < min) max = min;
        }

        return max;
    }
}