Programmers > Sort > #21 H-Index [JAVA]

H-Index

 

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

 

 

 

 

 

 

1. 문제 설명

 

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

 

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

 

 

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

 

 

2. 나의 코드

 

- 해당 요소의 값보다 해당 요소이하의 갯수(Index)가 커야함

- 내림차순으로 정렬 후에, 배열의 요소와 Index를 하나씩 비교해본다.

- 만약 Index > element 가 된다면, answer = index가 되고 빠져 나온다.

- H-Index 값과 배열의 길이가 같은 경우, 예를 들어 [3, 2] 인 경우 H-Index는 2이지만 배열의 길이가 짧아서

Index가 3일때 배교를 제대로 하지 못한다. 따라서 for문에서 arr.size()+1을 해서 비교를 할 수 있도록 한다.

 

 

 

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        //array descending sort
        ArrayList<Integer> arr = new ArrayList<>();
        for(int k =0; k < citations.length; k++){
            arr.add(citations[k]);
        }
        
        Collections.sort(arr);
        Collections.reverse(arr);
        
        for(int i = 0; i < arr.size()+1 ;i++){
            if(i == arr.size()){
                answer = i;
            }
            else if(arr.get(i) <= i){
                answer = i;
                break;
            }
        }
        return answer;
    }
}

 

 

2)

- 이 코드는 테스트 케이스에서는 백프로 잘되는데, 실제 실행 해보면 하나도 안되는 코드이다.

- 진짜 이거 왜 안되는지 몰랐는데, 10시간 고민하고 알게 되었다.

- i+1(요소의 실재 갯수)을 배열요소와 비교해서 element < index 를 충족하면, answer = element 를 리턴하도록 하는 코드.

- [10] 인 경우, H-Index는 1이다. [5,5,5,5] 인 경우 H-Index는 0이 아니라 4이다. 하지만 모두 0을 리턴한다. 

- index를 기준으로 H-Index가 판별된다.

 

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        //array descending sort
        ArrayList<Integer> arr = new ArrayList<>();
        for(int k =0; k < citations.length; k++){
            arr.add(citations[k]);
        }
        
        Collections.sort(arr);
        Collections.reverse(arr);
        
        for(int i = 0; i < arr.size() ;i++){
             if(arr.get(i) <= i+1){
                answer = arr.get(i);
                break;
            }
        }
        return answer;
    }
}

 

3. 다른사람 코드

 

- 굳이 descending sort를 하지 않아도, ascending sort로 더 간단하게 정렬할 수 있다.

- 끝 index와 첫 element를 비교하면서 둘 중 작은 수를 추출한다.

- 추출 된 수를 result에 넣고, 다음에 추출된 수와 비교하여 그중 큰수를 다시 result에 넣는다.

- 이를 반복한다. 

- 전체 배열의 갯수와 요소의 값과 일치하는 것을 찾는 과정.

 

e: [0,1,3,5,6]

i: 5 4 3 2 1

 

=> 어떻게 이런 생각을 했는지 정말 대단하다...

 

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);
            answer = Math.max(answer, smaller);
        }
        return answer;
    }
}

 

3. 보완

 

문제 풀때, 집중!