[프로그래머스 42747 파이썬] H-Index (level 2, 정렬)

알고리즘 유형 : 정렬
풀이 참고 없이 스스로 풀었나요? : O

https://programmers.co.kr/learn/courses/30/lessons/42747?language=python3#

SOLVE 1

정렬 풀이

def solution(citations):
    citations.sort()
    
    for i in range(len(citations), -1, -1):
        if citations[-i] >= i:
            return i

SOLVE 2

enumerate 풀이

def solution(citations):
    citations.sort(reverse = True)
    
    answer = max(map(min, enumerate(citations, start = 1)))
    return answer

SOLVE 1) 풀이 요약 (정렬 풀이)

1. citations를 오름차순으로 정렬한다.

2. citations의 길이에 따라 최대 H-Index부터 가능한지 여부를 for로 돌면서 판별해나간다.

   citations : [3, 0, 6, 1, 5]
   return : 3

   테스트케이스에서 논문이 5편이므로, 5부터 판별해나간다.

   오름차순 정렬했기에 citations는

   [0, 1, 3, 5, 6]

   첫 번째 요소부터 진행한다.

   만약 첫 번째 논문의 인용 횟수가 5 이상이면, 정렬에 따라 그 뒤에 논문들도 전부 인용 횟수가 5 이상이므로 H-Index의 최대값은 5가 된다.

   아니라면 H-Index가 5가 되는 것은 불가능하므로 다음 논문으로 넘어간다.

   이런 원리를 마지막 논문까지 진행한다. 다만, 모든 논문의 인용 횟수가 0인 경우가 있을 수 있으므로, for문을 0까지 돌아서 첫 번째 요소가 인용 횟수가 0인 경우를 검사하도록 작성한다. 이 떄의 H-Index는 0이다.

SOLVE 2 풀이 요약 (enumerate 풀이)

1. 위 풀이와 원리는 비슷하다.

2. citations : [3, 0, 6, 1, 5]
   return : 3

   이 테스트케이스에서 내림차순으로 정렬해보자.

   [6, 5, 3, 1, 0]

   이 후, enumerate로 튜플을 만든다. start = 1로 지정한다. 0번째 수는 내림차순 정렬된 citations에서, 자신보다 인용 횟수가 크거나 같은 논문의 개수를 의미하고, 1번째 수는 자신의 인용 횟수를 의미한다.

   (1, 6), (2, 5), (3, 3), (4, 1), (5, 1)

   임의의 튜플에 대해 min 값을 취한다.

   만약 왼쪽의 수가 min이라면, 이는 왼쪽 수 k에 대해, 현재 논문부터 순서 상 왼쪽에 위치한 모든 논문의 인용 횟수가 모두 k 이상이고, 그 논문의 개수는 총 k개라는 뜻이다. 즉, H-Index의 후보군으로 k가 가능하다는 것을 알 수 있다.

   이 로직을 모든 논문에 대해 실행하고, 구한 모든 후보군 중 최대값이 구하는 H-Index이다.

배운 점, 어려웠던 점

• enumerate의 신박한 활용을 배울 수 있어 유익했다.