프로그래머스 알고리즘 고득점 Kit - [Lv.2] H-Index (Java)

문제 출처 - 링크

알고리즘 분류

• 정렬

📋 문제 요약 설명

• 과학자가 발표한 논문 중 h번 이상 인용된 논문이 h번 이상일 때 h를 구하라.

💡 알고리즘 설계 / 접근 방법

1. 논문이 인용된 수가 담긴 배열을 내림차순으로 정렬한다.
2. 가장 많이 인용된 논문 수와 배열의 값을 비교하면서 h번 이상 인용된 논문이 h번 이상일 때를 구한다.

✅ 풀이

시간 복잡도 → O(N log N + N × M) → O(N × M) (정렬보다 탐색이 훨씬 크므로)

제한 조건 상으로는 문제가 없지만 비효율적인 방식이다.

1. 정렬 : O(N log N)
2. while 문 : 최악의 경우 O(N × M)
   • maxUse는 가장 큰 인용 수부터 0까지 : 최악의 경우 M(최대 10,000번)
   • for 루프는 매번 전체 배열을 순회 : O(N)
   • N : 논문 수 (최대 1,000)
   • M : 최대 인용 수 (최대 10,000)

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        // int형 내림차순 정렬은 Integer로 가능해서 형변환 해야함
        Integer[] desc = Arrays.stream(citations).boxed().toArray(Integer[]::new);
        Arrays.sort(desc, Collections.reverseOrder());
        int maxUse = desc[0]; // 가장 많이 인용된 논문 수

        while (0 <= maxUse) {
            int count = 0; // 인용된 눈문 수
            for (int i = 0; i < citations.length; i++) {
                if (maxUse <= desc[i])
                    count++;
            }
            //System.out.println(maxUse + " : " + count);
            if (count >= maxUse) // h(count)번 이상 인용된 논문이 h(maxUse)편 이상이면
                return maxUse;
            maxUse--;
        }
        return maxUse;
    }
}

➕ 개선하기 / 성능 비교

• 정렬의 개념을 사용해서 좀 더 간단한 방법으로 문제를 다시 풀었다.
• 코드 풀이
  • 정렬했기 때문에 citations.length - i 편은 모두 citations[i] 번 이상 인용되었음을 의미한다.
    • 문제의 예 : i가 1이면, 4편은 모두 citations[1] = 1번 이상 인용되었다.
  • 오름차순 정렬을 통해 큰 값들이 뒤로 몰려 있기 때문에, h <= citations[i]를 만족하는 순간 가장 큰 h를 찾은 것이 된다.
    • 이 시점에서 h편 이상이 h번 이상 인용되었음을 의미한다.

시간 복잡도 → O(N log N)

1. 정렬 : O(N log N)
2. for 루프 : O(N)

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        // 두 번째 풀이
        Arrays.sort(citations);  // 오름차순 정렬

        for (int i = 0; i < citations.length; i++) {
            int h = citations.length - i; // 현재 인덱스보다 오른쪽에 있는 논문 개수

            if (h <= citations[i]) { // h번 이상 인용된 논문이 h편 이상이면
                return h;
            }
        }
        return 0;
    }
}