[프로그래머스] H-Index

출처:: programmers.co.kr/learn/courses/30/lessons/42747#

분류:: 정렬

 

1. 문제 이해 및 해결과정

1)  이분탐색

- 이분탐색으로 풀이하였다.  - 테스트케이스 16에서 실패했었는데, [0,1,1] 1 을 고치니 해결이 되었다 -> hindex함수에서 index의 초기값때문에  if len(citations)-index>=mid 가 참이 나올 수 있는 경우 때문이였다. 초기 index를 10000으로 설정해주어서 해결  - ex) [3 0 6 1 5] -> (정렬) [ 0 1 3 5 6 ] ->         len=5 이므로 mid가 2부터 시작 , 3>=2 이므로, index=2 이고, 5-2 >= 2 이므로 ,True         s+e = 3+5 //2  = 4, mid=4, 5>=4 이므로, index=3이고, 5-3>=4이 성립하지 않으므로 False, e= 3         s+e = 3+3 //2 = 3 , mid  = 3 , 3>=3 이므로, index = 2 이고, 5-2>=3 성립하므로, True , res = 3

2) 정렬

- 굳이 이분탐색으로 풀지 않고 , 논문의 인용횟수가 h보다 큰 것을 찾으면 된다

 

2. 풀이방법

 1. [python] 이분탐색

def hindex(mid,citations): #hindex가 가능한지를 판별하는 함수
    index=10000 #mid보다 작은 값들, 큰값들을 분리하기위한 인덱스
    for i in range(len(citations)):
        if citations[i]>=mid: #mid보다 같거나 큰 부분이 나올경우
            index=i
            break
    if len(citations)-index>=mid:# h번(mid) 이상 인용된 논문이 h편(mid)이상이라면 
        return True
    return False
    
def solution(citations):
    #1.논문의 인용횟수 정렬
    citations.sort()
    s,e=0,len(citations) #h-index가 가능한 범위는 0~논문의 수 
    res=0 #hindex
    #2. 이분탐색 
    while s<=e:
        mid=(s+e)//2
        if hindex(mid,citations) :  #h인덱스가 가능하면
            s=mid+1
            res=mid
        else: #불가능하면
            e=mid-1
            
    return res

2. [python] 정렬

def solution(citations):
    citations.sort()
    n=len(citations) #논문의 수
    
    for i in range(n):
        if citations[i]>=n-i: #citations[i]보다 크거나 같은 논문이 n-i개 있다면
            return n-i
    return 0

 

3. 오답원인

 

4. 알게된 점