Leetcode Java H-Index II

문제

Link

코드

class Solution {

  public int hIndex(int[] citations) {
    int length = citations.length;
    int left = 0;
    int right = length - 1;
    while (left <= right) {
      int mid = (left + right) / 2;
      int diff = length - mid;
      if (citations[mid] == diff) {
        return diff;
      } else if (citations[mid] < diff) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return length - left;
  }

}

결과

Link

설명

1. 지난번 H-Index와 비슷한 문제로, 각 논문의 인용 횟수인 주어진 정수 배열인 citations으로 H-Index를 구하는 문제이다.
   • 전문적인 내용으로 해석이 까다로운 문제이므로 간단히 설명하면, citations의 길이보다 작은 크기에서 최대 인용 가능한 횟수를 구하는 문제이다.
   • 단 지난 번 문제와 다른 점은, citations가 오름차순으로 정렬되어 있다는 것이다.
2. 문제 풀이에 필요한 변수를 정의한다.
   • length는 citations의 길이를 저장하는 변수이다.
   • left는 binary search에서 좌측에서 시작하는 index로, 0으로 초기화 한다.
   • right는 binary saerch에서 우측에서 시작하는 index로, $length - 1$로 초기화 한다.
3. left가 right보다 같거나 작을때 까지 반복을 수행한다.
   • mid에 $\frac{left + right}{2}$ 값을 넣어 left와 right 가운데의 index를 정의한다.
   • diff에 $length - mid$ 값을 넣어 h-index 값을 임의 정의한다.
   • citations[mid]의 값이 diff와 동일하면 diff의 값이 h-index이므로, diff를 주어진 문제의 결과로 반환한다.
   • citations[mid]의 값이 diff보다 작으면 left에 $mid + 1$의 값을 넣어 탐색 범위를 축소시킨다.
   • citations[mid]의 값이 diff보다 크면 right에 $mid - 1$의 값을 넣어 탐색 범위를 축소시킨다.
4. 반복이 완료되면 citations의 값으로 h-index를 탐색하지 못하였으므로, $length - left$의 값을 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.