[JAVA][프로그래머스][정렬] H-Index

원사이트 : https://programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index | 프로그래머스

1.문제설명

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

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

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

2.제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

3.입출력 예

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

4.풀이(JAVA)

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        int compareCount = 0;
        int arrayLength = citations.length;
        
        
        for(int i=1; i<=arrayLength; i++){
            int comapreValue = i;
            compareCount = 0;
            for(int j=0; j<arrayLength; j++){
                if(citations[j] >= comapreValue) compareCount++;
            }
            
            if(compareCount>=comapreValue && comapreValue>= (arrayLength-compareCount)){
                answer = comapreValue;
            }
        }
           
        return answer;
    }
}

5.다른 사람 풀이

import java.util.*;

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;
    }
}

 

6.분석 및 개선점

(4의 분석)

1. n개의 배열에 n번의 검사를 2번 실행하여 최댓값 결과 반환. (선택정렬 2번 사용)

 

(5의 분석)

1. Arrays.sort()를 이용하여 오름차순 정렬(퀵정렬)

2. 주어진 문제(h-index)의 특성을 이용한 선택정렬을 하여 h-index값 도출.

 - 3의 입출력예를 들어 설명을 해보자.

 - 역순으로 탐색을 시작하는 경우 가장 큰 수에 대하여 최소 h-index는 1번이 된다.

 - 위 의 말을 식으로 정리하면 N크기의 배열에 대하여 h-index는 최소 N-(N-1)이 보장되기에 역순으로 값을 찾는 식을 사용.

 - h-index의 특징인 h편의 논문이 h편이상 인용 나머지가 h편이상이 되는 조건을 충족하기 위해 두 수중 최소값 중에서 가장 큰 값을 h-index를 사용

 

(4의 풀이 개선점)

1. 코드가 간결하지 못하여 가독성이 떨어진다.

2. 5의 풀이의 경우 n길이의 배열엥 대하여 2번 정렬은 하나 1번은 Array.sort()로 정렬하기에

퀵정렬이 적용되어 내 풀이보다 빠른 속도를 기대할 수 있는 반면에 

4의 풀이에는 선택정렬을 2번 사용한 방식으로 무조건 N x N번의 탐색을 진행하기에

속도 측면에서 5번보다 효율적이지 못할 수 있다.

(단, 5의 풀이는 min함수를 매번 호출하는 점에서 이슈가 있을 수 있다.)