프로그래머스 H-Index in Java

문제

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

접근

먼저 배열을 정렬해야 풀리겠다는 생각은 바로 들어서 정렬하고 for 문으로 돌면서 인덱스와 배열의 값이 같은지 확인했지만 주어진 하나의 테스트케이스만 만족하고 실패했다. 생각해보니 {15,16,17,18} 같은 경우에는 4가 정답이 되기 때문에 잘못된 접근이었다. 문제 자체를 제대로 이해하지 못한 것이다.

다시 생각해보니 정답은 citations.length 내의 값일 것이고 거꾸로 순회해야한다는 생각이 들어서 다시 코드를 작성했다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int[] sorted = Arrays.stream(citations).sorted().toArray();
        int answer = 0;
        for(int i=sorted.length-1; i>=0; i--){
            if(sorted[i] >= answer){
                answer++;
            }
        }
        return answer;
    }
}

이렇게 작성해보았다. 하지만 테스트케이스 11, 16번을 통과하지 못했고 질문하기 탭을 통해 추가적인 테스트케이스를 얻었다. 그리고 for문 내 if 문 조건에 sorted[i] > i라는 조건을 추가하였지만 11번을 여전히 통과할 수 없었고 이유는 {2, 2, 2, 2, 2} 의 경우에 답이 2여야 하는데 3이 나오는 것이 문제였다. 해법은 sorted[i] >= answer가 되는 마지막 조건을 만족하는 순간 break를 추가하여 멈춰주어야 했다. 구글링을 통해 이곳에서 해법을 확인할 수 있었다.

통과한 코드는 아래와 같다.

import java.util.*; 

class Solution {
    public int solution(int[] citations) {
     int[] sorted = Arrays.stream(citations).sorted().toArray();
       int answer = 0;
       for(int i=sorted.length-1; i>=0; i--){
          if(sorted[i] > answer){
             answer++;
          }else{
              break;
          }
       }
      return answer;
    }
}

11번, 16번 케이스가 안된다면
[2, 2, 2, 2, 2] => 2
[0, 1, 1] => 1
케이스를 추가하면 해결할 수 있다.