[프로그래머스 / Level2] H-Index (Java)

문제

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

코딩테스트 연습 - H-Index

 

H-Index : 과학자의 생산성과 영향력을 나타내는 지표.
= 어떤 과학자가 발표한 논문 n편 중, h회 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었을 때, h의 최대값.

 

풀이

전체 논문의 인용횟수를 값으로 가진 배열에서 "전체 n편 논문 중 h편의 논문이 h회 이상 인용되었다." 조건에 부합하는 h를 찾아야한다. 이 때, 과학자가 발표한 전체 논문 수 n과 H-Index가 될 수 있는 h의 관계는 [h <= n]

 

1. 인용횟수 배열 정렬

'~이상인 요소의 개수' 를 구해야하기 때문에 일단 배열의 요소를 정렬해야 한다.

Arrays.sort(citations);		// 배열 오름차순 정렬

 

2. 인용횟수 배열 요소 값을 차례로 h로 지정하며 H-Index 조건 여부 파악

(해당 요소의 논문 인용 횟수 >= h회 이상 인용된 논문 개수) 조건에 부합하면 해당 차례에서  'h회 이상 인용된 논문 개수'가 H-Index이다.
'h회 이상 인용된 논문 개수' : 오름차순 정렬했을 때,  해당 요소부터 마지막 요소까지의 요소 개수

입력 값이 {4, 0, 6, 1, 5} 일 경우, 배열을 오름차순 정렬하면 {0, 1, 4, 5, 6}이 된다.
여기서 각 값보다 인용횟수가 크거나 같은 논문 편수를 h로 잡고, H-Index 조건을 체크해보면 조건에 부합하는 값 중 최대값인 H-Index는 3인 걸 알 수 있다. (*h는 citations[i] 보다 작거나 같은 수이다.)

해당 논문 인용 횟수 = citations[i]	해당 논문보다 인용횟수가 크거나 같은 논문 편수 = h	h회 이상 인용된 논문 편수가 h편 이상이다. (true/false)
0	5	5회 이상 인용된 논문 편수가 5편 이상이다. => false
1	4	4회 이상 인용된 논문 편수가 4편 이상이다. => false
4	3	3회 이상 인용된 논문 편수가 3편 이상이다. => true 4회 이상 인용된 논문 편수가 3편 이상이다. 는 말도 true가 되지만 조건이 'h회 이상 인용된 논문 편수가 h편 이상' 이기 때문에 '인용된 횟수'와 '논문편수' 값이 h하나로 일치해야 되기 때문에 H-Index가 될 수 있는 최대값은 3일 수밖에 없다.
5	2	2회 이상 인용된 논문 편수가 2편 이상이다. => true
6	1	1회 이상 인용된 논문 편수가 1편 이상이다. => true

 

코드 1

해당 논문보다 인용횟수가 크거나 같은 논문 편수를 h로 잡고, citations[i] 값이 h 보다 크거나 커서 조건문에 만족하는 순간의 h값을 answer로 반환한다. 조건에 처음으로 만족하는 순간이 H-Index 최댓값이고 이후로는 무조건 h값이 작아지기 때문에 이후의 차례는 체크할 필요가 없다.

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);

        for (int i = 0; i < citations.length; i++) {
            int h = citations.length - i;   // 논문 개수

            if(citations[i] >= h){
                answer = h;
                break;
            }
        }

        return answer;
    }
}

 

코드 2

'현재 논문의 인용횟수'와 '현재 논문보다 인용횟수가 크거나 같은 논문의 편수' 두 값 중 작은 쪽을 H-Index로 지정해야 "h회 이상 인용된 논문의 편수가 h편 이상"이라는 말이 무조건 참이 될 수 있기 때문에 두 값 중 최솟값으로 임시 H-Index를 지정하고, 오름차순으로 정렬된 요소들에 차례로 접근해 최댓값을 갱신해나간다. 이렇게 최댓값을 갱신해 나가다 더 이상 값이 증가하지 않고, 감소되는 구간에서 반복을 중지하고(이후 차례부터는 값이 계속 감소할 것이기 때문에 비교할 필요가 없음) 이전 차례에 저장된 answer값을 그대로 반환한다.

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        for(int i=0; i<citations.length; i++){
            int smaller = Math.min(citations[i], citations.length-i);
            
            if(smaller >= answer)
                answer = Math.max(answer, smaller);
            else
                break;
        }
        return answer;
    }
}