[프로그래머스] H - Index (Python)

📌 문제

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

📌 문제를 이해해보자

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

글을 읽어도 이해가 잘되지 않습니다. 때문에 숫자를 대입해 예시를 생각하겠습니다. 논문이 4편이 중, 2번 이상 인용된 논문이 2편 이상이고 나머지 논문이 2번 이하 인용되었다면 2가 결과 값입니다.

• 이때 우리는 이상이라는 말에 주목해야합니다. 2번 이상 인용된 논문이 2편 이상이면 3편, 4편도 포함합니다.
• 최대값을 구하는 문제이기 때문에 거꾸로 탐색하는 것이 좋습니다.

📌 생각 과정

• 리스트로 입력 되었을 때, 우리는 인덱스 차례로 값들을 비교하며 갱신해야합니다.
• h-index를 가정하고 조건을 만족하고 최대값이라면 반환하는 형태를 만듭니다.
• 이때, h - index는 논문의 갯수보다 작기 때문에 가능한 최대값은 논문의 갯수이다.
• 1편이 0번 인용 되었으면? -> 0 때문에 최소값은 0이다.

📌 알고리즘

1. h - index를 가정한다.
2. 논문의 반복 횟수를 탐색한다.
3. 가정한 h - index 값 이상 인용된 논문을 카운트 해준다.
4. 카운트가 논문의 갯수가 가정한 h - index 값보다 크다면 h - index가 될 수 있다.
5. h - index 0~논문갯수에 대해서 가정하며 최대값을 찾아준다. 

def solution(citations):
    if sum(citations) == 0:
        cnt = 0
        return cnt
        
    for i in range(len(citations),0,-1): # h편의 논문
        cnt = 0
        
        for j in citations: # h편 이상 인용
            if j >= i:
                cnt += 1 # h편 이상 인용된 논문의 갯수
        if i <= cnt:
            return i

📌 다른 풀이

1. 오름차순으로 정렬한 뒤 풀이과정

def solution(citations):
    citations.sort()
    for idx , citation in enumerate(citations):
        if citation >= len(citations) - idx :
            return len(citations) - idx
    return 0

🤔 이해하기

1. 오름차순으로 정렬한다.
2. 인덱스와 오름차순으로 정렬된 반복된 인용 횟수를 호출한다.
3. 인용 횟수가 오름차순에 남아있는 논문의 갯수보다 크다면 h-index의 최대값은 이전의 논문의 인덱스값이 될 것이다.

🤔 어떤 로직을 암기할까?

정렬된 리스트에서 인덱스값과 해당값의 비교를 통해서 남아 있는 값들의 최대값 혹은 최소값을 알 수 있다.

2. 내림차순으로 정렬한 뒤 풀이과정

def solution(citations):
    citations.sort(reverse=True)
    for idx , citation in enumerate(citations):
        if idx >= citation:
            return idx
    return len(citations)

참고 코드 출처