❓프로그래머스 : H-Index

📈 문제 요약

h번 이상 피인용된 논문이 h개인 경우 저자의 H-Index는 h일 때 H-Index를 구하면 되는 문제

1️⃣풀이 1 : 파라메트릭 서치(매개변수 탐색)를 활용한 풀이

🤨 접근법

def is_h(h, citations):
    return len([i for i in citations if i >= h]) >= h

각 논문 별 피인용된 횟수가 들어있는 citations배열에서 h보다 높은 논문이 h개 있는지 결정하는 문제를 통해 최대 h를 구했다.

def solution(citations):
    low, high = 1, len(citations)
    
    while low <= high:
        mid = (low+high)//2
        if is_h(mid, citations):
            low = mid+1
        else:
            high = mid-1
    return high

h는 1부터 논문의 개수 만큼의 범위를 가지고 있고, 최대 h 즉 H-Index 이하의 h들은 모두 위 결정 문제를 만족한다. 따라서 이분탐색으로 범위 내 수를 결정 문제에 넣어 만족하는지 확인 후, 만족한다면 h를 더 높여보고(low = mid + 1), 만족하지 않는다면 h를 더 낮춰봐서(high = mid - 1) 탐색한다.

이때 low가 high를 역전하면 탐색을 종료하며, 최대 h는 high에 담겨 있다.(과정 참고)

2️⃣풀이 2 : 정렬을 활용한 풀이

🤨 접근법

본 문제 유형은 정렬에 속하고, 풀이 1에서의 풀이는 정렬을 활용한 풀이가 아니기 때문에 정렬을 활용한 풀이도 정리해보려 한다.

피인용횟수가 들어있는 배열을 내림차순으로 정렬하게 되면 배열의 값만큼 인용된 논문이 인덱스+1만큼 있다라는 의미로 해석이 가능하다.

즉, citations 배열을 순회하며 인덱스를 i라고 할때 citations[i]가 처음으로 i+1보다 작아지면 citations[i]만큼 인용된 논문이 i개 있다고 할 수 있다.

🔡 코드

def solution(citations):
    citations.sort(reverse = True)
    for i in range(len(citations)):
        if citations[i] < i+1:
            return i
    return len(citations)