프로그래머스 lv2 - H-Index (자바)

문제

---

프로그래머스 lv2 - H-Index

풀이

---

이분탐색

• 문제에서 h의 최댓값을 요구하므로 h의 값을 이분탐색의 기준으로 한다.
• h(논문별 인용 횟수)는 0회 ~ 10000회 이므로 lo = 0, hi = 10000으로 잡고 이분탐색 시작
• h의 최대값을 구하는 것이므로 h가 조건에 맞다면 h를 갱신한 후 lo를 h + 1로 옮김
• h가 조건에 맞지 않으면 hi를 그 시점 h - 1로 옮김

코드

---

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);

        int lo = 0, hi = 10000;
        int mid = 0;
        while (lo <= hi) {
            mid = (lo + hi) / 2; // h편 
            if (check(mid, citations)) {
                answer = mid;
                lo = mid + 1;
            } else
                hi = mid - 1;
        }

        return answer;
    }

    boolean check(int h, int[] citations) {
        int[] cnt = new int[2];
        for (int i = 0; i < citations.length; i++) {
            if (h <= citations[i]) // h번 이상 인용
                cnt[0]++;
            else if (h >= citations[i]) // h번 이하 인용
                cnt[1]++;
        }
        return (cnt[0] >= h) && (cnt[1] <= h);
    }
}