[Programmers] H-index.py (sort)

#. Problem

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

* The copyright in this matter is in Programmers

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 

어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, 

h번 이상 인용된 논문이 h편 이상이고 

나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때,

이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - h번 이상 인용된 논문이 h편 이상, 나머지 논문이 h번 이하 인용

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. citations list를 우선 정렬

  2. h를 0부터 시작하여, h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하인지 확인

    f (A) = 10, f (B) = 8, f (C) = 5, f (D) = 4, f (E) = 3 → h- 색인 = 4

    f (A) = 25, f (B) = 8, f (C) = 5, f (D) = 3, f (E) = 3 → h- 색인 = 3

    - wikipedia를 보면 test case가 나와있는데 결국은 h가 될 수 있는 최댓값을 구하는게 중요한듯 하다.

#. Code

1 2 3 4 5 6 7

def solution(citations):     citations.sort(reverse=True)     ln = len(citations)     for i in range(ln):         if citations[i] <= i:             return i     return ln

cs

  - 무엇보다 문제를 이해하는게 너무 힘들었다.. 설명 부분에서도 그렇고..

    wikipedia를 참고하면, 먼저 citations를 내림차순으로 정렬하라고 나온다.

    그런 다음 citations의 요소 중 위치보다 작거나 같은 마지막 위치를 찾으면 된다고 한다.

    결국, 중요한건 citations의 요소와 위치의 비교인 것이다.. 

    (2) 먼저 citations를 내림차순으로 정렬

    (4~6) citations의 요소와 위치를 비교한다. index의 값이 index보다 작다면 index를 return 해준다.

           (index가 더 커야하는 이유는 index는 즉 h이므로 자리값보다 커야 h가 그 자리값 이상이라는 것을 알 수 있다.

            [6, 5, 3, 1, 0]일 때, index(h)=3이라면, citations[index]=1이 된다. 여기서 h는 1보다 커야하는 조건을 만족해야 하고, 

            동시에 index가 3까지 왔다는 것은 h 이상인 요소가 3개가 있다는 것을 충족시킨다.)

    (7) h가 구해지지 않은 경우는 모든 논문이 citations의 크기만큼인 경우

  [ citations[i],  i  ]

         6    0

         5    1

         3    2

         1    3   -> i가 같거나 커지는 지점

         0    4

#. Others code

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

  - citations를 오름차순으로 정렬했을 경우, citations[i]와 l-i의 변화는 아래와 같다

    여기서는 l-i를 citations[i]의 값보다 크거나 같은 요소의 개수라고 생각하면 접근하기 더 쉬운 것 같다.

    인용된 논문이 모두 0편일 경우 return 0을 사용해주는 것 같다.

    [ citations[i],  l-i ]

           0 5

           1 4

           3 3  -> l-i가 작거나 같은 지점

           5 2

           6 1

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

  - 위 코드에서 발견한 규칙을 이해해야만 이렇게 풀 수 있을 것 같다..

    index와 citations[index]를 비교하는 리스트를 생성한 후 -> [(1, 6), (2, 5), (3, 3), (4, 1), (5, 0)]

    각 튜플에서 최솟값을 구한 결과에서 -> [1, 2, 3, 1, 0]

    최대 값을 추출 -> 3