프로그래머스 | H-index [파이썬 python]

프로그래머스

 

코드

def solution(citations):    
    for h in range(max(citations), 0, -1): # h(범위: 최대 인용 횟수부터 1까지) '역순' 순회
        count = 0  # h번 이상 인용된 논문 수
        for c_num in citations:
            if h <= c_num: # 인용 수가 h 이상이면 count +1
                count += 1
        if count >= h: # 가장 먼저 h번 이상 인용된 논문수가 h번 이상이면 리턴
            return h
    
    return 0

논문 n 편 중, h번 이상 인용된 논문이 h 편 이상이 될 수 있는 h의 최댓값을 구해야 하는 문제이다.

먼저 문제 이해를 위해 필기한 과정을 설명하면 다음과 같다.

주어진 citations을 오름차순으로 정렬한다.

h를 인용 횟수라고 생각할 때, 주어진 citations에서 h의 범위는 최소 0번에서 최대 max(citations)가 될 수 있다.

citations=[3,0,6,1,5] 일 때 h의 범위는 0에서 6까지의 정수이다.

각 h마다 조건을 만족하는지 확인한 뒤 최종적으로 h의 최댓값을 찾으면 된다.

위 그림에서 h=4일 때는 4번 이상 인용된 논문의 수가 [5, 6]으로 2개이므로 h=4보다 작아진다.

문제에서 h번 이상 인용된 논문의 수가 h 이상이어야 하므로 조건에 맞지 않는다.

따라서 이 경우 h의 최댓값은 3이 된다.

 

우리가 구해야 하는 것은 h의 최댓값이다.

그러므로 h를 0부터 시작하는 것이 아닌 max(citations)부터 시작하면 더 빠르게 h의 최댓값을 찾을 수 있다.

따라서 h를 순회하는 for문의 범위를 다음과 같이 (max(citations), 0, -1)로 역순 순회 할 수 있도록 해준다.

for h in range(max(citations), 0, -1): # h(범위: 최대 인용 횟수부터 1까지) '역순' 순회
    count = 0  # h번 이상 인용된 논문 수
    for c_num in citations:
        if h <= c_num: # 인용 수가 h 이상이면 count +1
            count += 1
    if count >= h: # 가장 먼저 h번 이상 인용된 논문수가 h번 이상이면 리턴
        return h

h번 이상 인용된 논문 수를 count라는 변수에 저장하고 주어진 citations의 요소를 하나씩 h와 비교하면 된다.

해당 논문의 인용수 c_num이 h이상이면 count+1을 해준다.

h를 max(citations)부터 역순으로 순회하므로 가장 먼저 count >= h가 되는 순간이 h의 최댓값이 된다.

 

lv2가 되니 머리를 써야 하는 문제가 자꾸 등장해서 머리가 아프다