[스위프트 알고리즘] 프로그래머스: H-Index

문제

문제 설명

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

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

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

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

풀이

h-index의 규칙이 h번 이상 인용된 논문의 개수가 h번 이상이 되는 최대값을 찾는 것이기 때문에, 단순히 오름차순, 내림차순으로 정렬한 뒤에 인덱스를 통해 특정 인덱스 이전에 논문이 몇개가 있는지 확인하는 것으로 해결할 수 있습니다.

 

저는 이번 문제가 이분 탐색으로도 풀이할 수 있을 것 같아서, 연습할겸 이분탐색으로 풀이했습니다. 따로 정렬을 하지 않고, 탐색할 대상을 배열의 인덱스로 정했습니다. 이분탐색을 통해 특정한 인덱스가 설정되면 해당 인덱스를 기준으로 논문의 개수를 카운트해서 만약 인덱스보다 발행된 논문의 개수가 같거나 많다면 탐색 범위의 왼쪽을 증가시키고, 작다면 탐색 범위의 오른쪽을 감속시켜 탐색범위를 좁혀나갑니다.

 

코드

import Foundation

func isHIndex (_ citations:[Int], _ index:Int) -> Bool {
    return citations.filter({ $0 >= index }).count >= index
}

func binarySearch (_ start:Int, _ end:Int, _ citations:[Int]) -> Int{
    
    var head = start
    var tail = end
    var mid = (start + end) / 2
    var hIndex = 0
    
    while head <= tail {
        mid = (head + tail) / 2
        if isHIndex(citations, mid) {
            head = mid + 1
            hIndex = mid
        }else {
            tail = mid - 1
        }
    }
    return hIndex
}

func solution(_ citations:[Int]) -> Int {
    return binarySearch(0, citations.count, citations)
}