[leetcode - 274. H-Index] java

문제 설명

1. 배열이 주어진다.

2. H-Index 란 내 논문의 인용수에서 n번 이상 된 것의 갯수가 n개 이상이 되는 최대의 n이다.

3. H-Index 를 구하면 된다.

풀이 과정 

1. 그리?디? 솔직히 걍 구현같다.

2. 최대 인용수를 구해서 거기서부터 확인해 본다.

3. 지금 논문의 인용수 n 이상의 논문 갯수를 보고, 이게 n보다 크거나 같으면 정답이 된다. (내림차순이므로 최대 보장)

4. pq 에 논문을 reverseOrder 로 저장하고 size를 확인하면 쉽게 구할 수 있다.

코드

class Solution {
    public int hIndex(int[] citations) {
        // 인용이 많이 된 것부터 저장한다.
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int max = 0; // 여기서부터 찾으면 된다.

        for(int i=0; i<citations.length; i++) {
            max = Math.max(max, citations[i]);
            pq.add(citations[i]);
        }

        int count = 0; // 현재 h-index 보다 많거나 같은 인용을 한 논문의 갯수 count
        for(int i=max; i>=0; i--) {
            while(!pq.isEmpty() && pq.peek() >= i) { // 현재 h-index 보다 인용을 많이 했거나 같은 인용이면 이건 count의 대상이 된다.
                count++;
                pq.remove();
            }
            
            if(count >= i) return i; // 그게 h-index 조건을 만족하면 돌려주면 된다.
        }

        return 0; // 하나라도 인용을 받은 논문이 있다면 여기로 도달할 수 없다. 여기는 인용을 아예 못받은 논문만 있을 때 도달한다.
    }
}