[프로그래머스] H-Index - Java

문제 : programmers.co.kr/learn/courses/30/lessons/42747?language=java

코딩테스트 연습 - H-Index

아이디어

Insertion sorting 방법을 이용하기

• n개의 논문 중 h회 이상 인용된 논문이 h개 이상일 때 그 h-index는 h이다. 따라서 h-index 값은 0 이상, n 이하가 된다.
• citations array를 역순으로 sorting 한 뒤, h값의 후보로 n부터 0까지(=candidate) 순회하면서 sorting된 array에 insertion sort를 수행했을 때, 이 candidate값이 들어가게 될 index를 찾는다.
• 만약 이 index값이 candidate 값보다 크다면, 예를들어 candidate값이 3인데 index값이 4라면, candidate값보다 높은 인용횟수를 가진 논문의 수가 4개라는 의미이므로, 이 경우 h-index는 3이 된다.
  • candidate는 n에서 시작해서 0을 향해 1씩 감소하며 순회하므로, 이 조건문이 성립하는 경우가 가장 큰 h-index가 된다. 따라서 조건문이 성립함과 동시에 반복문을 종료하고 찾은 h-index를 반환하면 된다.

소스코드

import java.util.Arrays;

public class Solution {
    public int solution(int[] citations) {
        // 역순정렬
        for (int i = 0; i < citations.length; i++) {
            citations[i] = -citations[i];
        }
        Arrays.sort(citations);
        for (int i = 0; i < citations.length; i++) {
            citations[i] = -citations[i];
        }

        int h;

        for (int i = 0; i < citations.length; i++) {
            int candidate = citations.length - i;
            h = this.findInsertionSortIndex(citations, citations.length - i);
            if (h >= candidate) {
                return candidate;
            }
        }

        return 0;
    }

    public int findInsertionSortIndex(int[] arr, int num) {
        // assume that the arr is already sorted in descending order
        for (int i = 0; i < arr.length; i++) {
            if (num > arr[i]) {
                return i;
            }
        }
        return arr.length;
    }
}