프로그래머스 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

 

틀린 풀이 1. 원래는 citations를 내림차순 정렬해서 인덱스 값과 비교하려고 했지만 citations가 int형 배열이라 다음과 같이 Comparator로 구현하면 오류가 났다(citations를 Integer 배열로 바꿔야 함)

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b-a; //내림차순
            }
        });
        ...
        return answer;
    }
}

 

틀린 풀이 2. 문제를 완전 잘못 생각했다... 원래는 6,5,3,1,0 이렇게 내림 차순으로 정렬 후에 citations[i] 와 i+1 을 비교해서 citations[i] <= i+1 인 경우 h를 citations[i]로 해서 풀었다.(h가 6,5,3,1,0 중에 하나라고 잘못 생각했다.) 그런데 이 경우 [15,16,17,18]이면 h가 4여야 하는데 이런 값을 제대로 도출해내지 못한다.  

 

맞는 풀이

: citations를 오름 차순으로 정렬한다.

예를 들어 [1,3,4,5,8] 이라고 하면 h는 0~5 중 하나의 값을 갖는다.

h가 각각 1~5일 가능성이 있는 경우를 보자. h = citations.length - i

1번 보다 많이 인용된 논문 수는 h=5   -> h가 5이면 5편의 논문이 5번 이상 인용되어야 한다. false

3번보다 많이 인용된 논문 수는 h=4    -> h가 4이면 4편의 논문이 4번 이상 인용되어야 한다. false

4번보다 많이 인용된 논문 수는 h=3    -> h가 3이면 3편의 논문이 3번 이상 인용되어야 한다. true

=> 이 경우 3편의 논문이 4번 이상 인용되었으므로 h의 최대값은 3이다.

5번보다 많이 인용된 논문 수는 h=2

8번보다 많이 인용된 논문 수는 h=1 이다.

 

즉, citations[i] >= h인 경우를 만족하는 h 값이 answer이다.

 

 

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