코딩테스트 연습 - H-Index

문제 풀이 아이디어

전형적인 파라메트릭 서치 문제입니다. 파라메트릭 서치는 특정한 하나의 값을 찾는 문제를 연속된 O / X 문제로 바꾸어서 이진탐색을 통해 그 값을 찾아나가는 알고리즘입니다.

어떤 값은 범위가 주어지면 그 값을 찾는 범위를 절반씩 줄여가면서 최적의 값을 찾아나가는 과정입니다.

이 문제는 h-index의 범위가 주어지고 어떤 값이 h-index가 될 수 있는지 O / X로 판정할 수 있는 조건이 주어져있습니다.

코드

import Foundation

func solution(_ citations:[Int]) -> Int {
    
    // 이진 탐색을 위한 양 끝 설정
    var start = 0
    var end = citations.max()!
    //👉 h-index는 가장 많이 인용된 논문의 인용 횟수를 넘을 수 없음!
    var ans = 0
    
    // 이진 탐색
    while start <= end {
        let mid = (start + end) / 2
        var cnt = 0
        
        // mid 이상 인용된 논문 갯수 세기
        for citation in citations {
            if citation >= mid { cnt += 1 }
        }
        
        // mid 이상 인용된 논문이 mid개 이상이라면 h-index의 조건 부합하므로
            // ans 갱신하고 더 높은 mid 탐색
        if cnt >= mid {
            start = mid + 1
            ans = mid
        // h-index의 조건에 부합하지 않으면 더 낮은 mid 탐색
        } else {
            end = mid - 1
        }
    }
    
    return ans
}