[Lv2.] 정렬 - H-Index

👉 사용 언어 : PYTHON3

H-Index

✅ Solution

def solution(citations):
    citations = sorted(citations, reverse=True)
    for i in range(citations[0], 0, -1):
        cnt = 0
        for j in citations:
            if j < i:
                break
            cnt += 1
        if cnt >= i and len(citations)-cnt <= i:
            return i
    return 0

 

👉 문제 설명 및 제한 사항

• H-Index는 과학자의 생산성과 영향력을 나타내는 지표
  • 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면,
  • h의 최댓값 이 이 과학자의 H-Index
• 매개변수 : 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations
  • 1 <= 길이 <= 1,000
  • 0 <= 원소 <= 10,000
• 리턴값 : 이 과학자의 H-Index

👉 아이디어

• citations 배열을 내림차순 으로 정렬한다.
• 배열의 max값 부터 -1 을 하며 0까지 반복문을 돌린다.
  • citations에서 큰값 부터 추출하여 i값이 같아질때까지  반복문을 돌리며 카운트 한다.
  • break 문이 걸리면 카운트 변수 cnt값이 i보다 크거나 같 고, citations 길이 - cnt값이 값보다 i보다 작거나 같 을 경우 i를 리턴한다. (= h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용)
• 만약, 반복문을 다 돌린 후에도 위의 조건을 만족하지 않는다면 0 을 리턴한다.
  • 테스트케이스 : [0, 0, 0, 0, 0] > 0

✅ 다른 사람 풀이 참고

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

• sort로 정렬해서 내림차순으로 정렬한후, enumerate 로 (index, value) 형태로 묶는다.
• 그리고 최댓값(start = 1)부터 각 value에 대해 최솟값을 min 으로 추출하고, 이 추출된 값은 enumerate 가 끝나는 citations 리스트의 크기 에 해당하는 갯수가 나온다.
• 이들을 map 으로 묶으면, 한 value의 입장에서 보는 최솟값의 집합 이 나온다.
• 즉 h값들의 집합이나온다. h값중 최대값 을 max 로 뽑아서 출력하면 된다.

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

 

:  [지금 몇 편이 남았는가? -> 모든 인용횟수가 이 값보다 큰가?(가장 작은 값이 이 값보다 큰가?)] 로 생각의 순서를 바꾼 것

 

👉 깨달은 것 / 알게된 것

• 배열.sort 과 배열 = sorted(배열)의 결과는 같다.
• 맨 위의 풀이에서는 정렬 + 중첩 반복문을 사용하여 시간복잡도상으로 효율적인 풀이 방법이 아니다.
  • 정렬 : O(n log n)
  • 중첩 반복문 : O(nm) < 첫 번째 반복문이 n번, 두 번째 반복문 m번일 경우