[PS] 99클럽 코테 스터디 12일차 TIL (H-index)

문제

문제 링크

발표한 논문 중 h 번 이상 인용된 논문의 갯수가 배열에 몇 개 있는지 확인 후 최대 값을 리턴해야 한다.

정렬하지 않고 푸는 방법

논문의 인용 횟수가 현재 배열에서 몇번 나왔는지 기록할 count 배열을 만든다. 이 배열의 인덱스가 인용 횟수(h)이며, 값은 해당 인용 횟수에 해당하는 논문의 수가 된다.

class Solution {
  public int solution(int[] citations) {
    int n = citations.length;
    int[] count = new int[n + 1];

    // 인용 횟수 카운트
    for (int c : citations) {
      if (c >= n) {
        count[n]++;
      } else {
        count[c]++;
      } 
    }
    
    // H-index 계산
    int total = 0;
    for (int i = n; i >= 0; i--) {
      total += count[i];
      if (total >= i) {
        return i;
      }
    }
    
    return 0;
  }
}

count 배열은 각 논문의 인용횟수에 대한 카운트를 저장하는 역할이기 때문에 크기는 n + 1 로 한다. 논문의 인용횟수가 논문 수를 초과하는 경우엔 count[n] 에 저장된다. 예를 들어, [3, 0, 6, 1, 5] 가 입력으로 주어졌을때 count 배열은 다음과 같은 순서로 채워진다.

// 3 위치 count+1 => 0 위치 count+1 => 6 위치 count+1 (5위치) => 1 위치 count+1 => 5 위치 count+1 
[0, 0, 0, 1, 0, 0] => [1, 0, 0, 1, 0, 0] => [1, 0, 0, 1, 0, 1] => [1, 1, 0, 1, 0, 1] => [1, 1, 0, 1, 0, 2]

• 0번 인용된 논문 갯수 : 1
• 1번 인용된 논문 갯수 : 1
• 3번 인용된 논문 갯수 : 1
• 5번 이상 인용된 논문 갯수 : 2

카운트 값을 뒤에서 부터 더하면 3번 이상 인용된 논문 갯수가 3일때 이 값이 h-index 가 된다.

정렬 후 풀이

큰 인용 횟수가 작은 인용횟수를 포함하므로 내림차순으로 정렬하면 쉽게 해결할 수 있다.

h	n
6	1
5	2
3	3
1	4

class Solution {
  public int solution(int[] citations) {
    int answer = 0;
    Integer[] array = Arrays.stream(citations).boxed().toArray(Integer[]::new);
    Arrays.sort(array, Collections.reverseOrder());

    for (int i = 0; i < array.length; i++) {
      if (array[i] >= i + 1) {
        answer = i + 1;
      } else {
        break;
      }
    }
    return answer;
  }
}