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

현재 논문이 가진 인용 횟수와 현재 위치부터 끝까지 남은 논문 수를 비교해서 H-Index를 구하는 문제.

 

1. 문제 유형

정렬, 배열, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 주어진 배열을 정렬한 뒤 중간값 비슷한 값을 기준으로 답을 찾으려고 했다.

오답 원인: 중요한 것은 "논문 h편이 각각 h번 이상 인용되었는가"이 배열의 중앙값이 아니다.

인용 횟수 자체가 아니라, 조건을 만족하는 논문 수를 함께 봐야 한다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 논문이 총 h편 이상 있고, 그 h편의 인용 횟수가 모두 h 이상이어야 한다.

풀이 아이디어:

1. 인용 횟수 배열을 오름차순 정렬한다.
2. 앞에서부터 탐색하면서 현재 논문의 인용 횟수를 확인한다.
3. 전체 논문 수 - 현재 인덱스 = 현재 논문을 포함한 남은 논문 수
4. 현재 인용 횟수 >= 남은 논문 수 조건을 처음으로 만족하는 순간 그 남은 논문 수가 H-Index다.

4. 구현 코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int currentNum = 0;
        
        Arrays.sort(citations);
        
        for(int i = 0; i < citations.length; i++) {
            currentNum = citations[i];
            if(currentNum >= citations.length-i){
                return citations.length-i;
            }
        }
            
        return 0;
    }
}

시간 복잡도: O (N log N) / 공간 복잡도: O(1)

---

 

인사이트

• 주어진 테스트 케이스에 의존하기보다 여러가지 테스트 케이스를 만들어서 테스트를 하는 것이 중요하다.
  참고 → https://school.programmers.co.kr/learn/courses/14743/lessons/118838

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42747