프로그래머스 H-Index

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42747#

문제 풀이

H-index의 크기를 이분 탐색을 이용해 구하는 방식으로 접근

valid_h_index 함수 : mid(h-index)가 주어졌을 때 citations 배열에서 mid보다 큰 수의 갯수가 mid보다 많을 경우 해당 값은 H-index로 사용가능

• 가능하다면 answer를 더 큰 값으로 교체해주고 값을 증가시켜 검사를 진행 (더 큰 값으로도 가능한지 판단하기 위해)
• 불가능하다면 값을 감소시켜 진행, 이 때 answer는 따로 할당이 필요없음.

function solution(citations) {
    var answer = 0;

    let left = 0;
    let right = citations.length;
    
    function valid_h_index(mid) {
        let valid_value = citations.filter(c => c >= mid).length;
        if (mid <= valid_value) {
            return true;
        } 
        return false;
    }

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (valid_h_index(mid)) {
            answer = Math.max(answer, mid);
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return answer;
}

---

결론

이분 탐색을 활용해 검사해야하는 h-index의 값의 범위를 줄여 접근