[PGS / 정렬] H-Index (java)

문제 보기

문제

• 입력 : 논문 인용 횟수 배열 citations[]
• 출력 : 논문 중, h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용된 h의 최댓값

문제 풀이

1. 이중 반복문 풀이

문제를 보고 스스로 푼 풀이는 다음과 같다.

h는 citations 원소 갯수 이하, 원소 최댓값 이하를 서로 만족해야 한다.
따라서, h가 될 수 있는 최댓값은 citations 원소 최댓값과 citations 배열 길이 중 작은 값이다. h 후보 최댓값부터 검사를 통해 값을 줄여가며 답을 구한다.

import java.util.*;

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

        Arrays.sort(citations); // 오름차순 정렬
        max = citations[length-1] < length ? citations[0]:length; // h 후보 최댓값 max
        int h = max;
        int idx = 0;
        
        // h 검사
        while(true){
            idx = 0; // h와 비교할 idx 및 횟수
            
            // h번 미만 인용논문 세기 검사
            while(citations[idx] < h) {
                idx++;
            }
            
            // h번 이상 인용된 논문 수(length-idx)가 h 이상 일 시, answer 도출
            if(length-idx>=h) {
                answer = h;
                break;
            }
            // h의 값 감소 후 h검사 다시
            else {
                h--;
            }
        }
        return answer;
    }
}

해당 코드에서, h 검사 while문에서 idx = 0부터 다시 논문 수를 세야 하는 것에 불필요성을 느꼈다. 뭔가 시간복잡도를 줄일 수 있을 거 같은데 더 생각나지 않았다..

성능 검사

O(n^2)

2. 단일 반복문 풀이

해당 풀이는 다른 사람의 풀이인데 훨씬 간단한 코드와 좋은 성능의 코드이다.

citations 배열을 조회하여, 해당 인덱스에서 가능한 H-Index 최댓값을 구하고, 이전 인덱스의 H-Index 값 후보와 비교해 갱신하는 과정을 거쳐 답을 도출한다.

import java.util.Arrays; 

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations); // 오름차순 정렬
        
        // 반복문을 통한 H-Index 계산
        for(int i=0; i<citations.length; i++){
            int smaller = Math.min(citations[i], citations.length-i);
            answer = Math.max(answer, smaller);
        }
        return answer;
    }
}

성능 검사

• 정렬 : O(nlogn)
• 반복문 : O(n)

=> O(nlogn)