[프로그래머스] H-Index

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

프로그래머스

 

접근

---

• citations 데이터로 점검할 경우, citations에 속하지 않는 인용 횟수에 대해 점검할 수 없다. 
• 주어진 범위 내에서 조건을 만족하는 최대 값을 찾는 것이 목표이므로, 이진 탐색을 사용할 수 있다. 

 

로직

---

• 논문 인용 횟수의 최솟값인 0과 최댓값인 10000을 경계로 하여 이진 탐색을 수행한다. 
• 조건을 만족하는 경우 max를 사용해서 갱신한다.
• 조건을 만족하는 경우 left 값을 mid + 1로 갱신, 만족하지 않는 경우는 right 값을 mid - 1로 갱신하여 이진탐색을 마저 수행한다. 

 

코드

---

def solution(citations):
    
    left = 0
    right = 10000
    
    result = 0
    
    while left <= right:
        mid = (left+right)//2
        up = 0
        down = 0
        
        for i in citations:
            if i >= mid:
                up += 1
            else:
                down += 1
                
        if up >= mid and down <= mid:
            result = max(result, mid)
            left = mid + 1
        else:
            right = mid-1
    
    return result

 

참고

---

• 기존 데이터의 순서를 지킬 필요가 없는 문제이므로 정렬을 사용할 수 있다. 

citations[i] >= l-i

• citations[i]는 논문의 인용 수
• l-i는 h번 이상 인용된 논문의 개수
• h번 이상 인용된 논문이 h편 이상인지를 점검하는 조건문이다.
• i-1까지의 데이터들은 정렬으로 인해 h번 이하 인용이 보장되어 있다. 

def reference(citations):
     citations = sorted(citations)
     l = len(citations)
     for i in range(l):
         if citations[i] >= l-i:
             return l-i
     return 0