algo lev-2 H-index (python)

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

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

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

출처 : 프로그래머스 Level2

내가 푼 풀이

• 문제를 푸는 것보다 문제를 이해하는데 더 시간이 많이 걸렸다
• 발표한 논문 n개 중에서, h번 이상 인용된 논문이 h편 이상, 나머지는 h번 이하로 인용
  • 이때 구하고자 하는 h가 발표한 논문의 인용 횟수와는 다르다는 점을 명심(!)
  • input : [22,24] output : 2
    • 2번 이상(22,24) 인용된 논문이 2편 이상이고(2편) 인용되지 않은 논문은 2편 이하 (0편)
    • 주어진 인용 횟수보다도 발표된 논문의 개수가 중요하다 (h의 기준점이 되니까)
    • 인용된 논문 개수 h개 == 인용된 횟수 h번 일치하는 지점을 찾자

1) num = 발표한 논문 개수 (가장 큰 h 값을 구하고 싶기 때문에 최대값부터 시작)

2) 오름차순으로 정렬된 citations 요소들과 num을 비교해서 citations[i] <= num < citations[i+1] 위치를 기준! 으로 num 번 이상 인용된 논문의 개수를 센다 (len())

• 성공!!!!

  def solution(citations):
      citations.sort()
      num = len(citations)
      while True :
          for i, value in enumerate(citations):
              if value >= num and len(citations[i:]) >= num :
                  return num
          else :
              num -= 1
              continue
          break
  

  • 지난 번 문제를 풀면서 배운 for-else를 이용해서 풀어봤다

• (수정) 시간복잡도 고려

  def solution(citations):
      citations.sort()
      num = len(citations)
      mid = num//2
      while True :
          if num >= citations[mid] : beg = mid; end = len(citations)
          else : beg = 0; end = mid
                
          for i in range(beg,end):
              if citations[i] >= num and len(citations)-i >= num :
                  return num
          else :
              num -= 1
              continue
          break
  

  • 시간복잡도를 고려해서 for 문의 수행 횟수를 줄이기 위해 beg와 end 값을 줬고
  • 리스트 슬라이스의 시간복잡도가 O(k)라 이를 줄이기 위해 len(citations)-i 라는 다른 값을 줬다 (k는 parameter의 개수나 element의 개수)
    • len()의 시간복잡도는 O(1)
  • 처음 풀이보다 시간이 줄어들었다 (70ms –> 4ms)

다른 사람의 풀이

• 훨씬 간결하고, 실행시간도 훨씬 줄어듬! (4ms –> 0.15ms)

  def solution(citations):
      citations.sort()
      l = len(citations)
      for i in range(l):
          if citations[i] >= l-i:
              # 논문이 인용된 횟수(h번 이상) >= 인용된 논문의 개수(h개 == h번)
              return l-i
      return 0
  

  • l-i == len(citations[i:])

  • 논문이 인용된 횟수(h번 이상) >= 인용된 논문의 개수(h개 == h번)

    • 오름차순으로 정렬해놨기 때문에 citations[i]는 그 이후 비교할 값들 중 최소값

  • EX) input : [22, 24] output : 2

    • citations[i] > len(citations) - i

    • ( i = 0 ) 22 >= 2-0

배운 점

• 어떻게 문제에 접근하고 풀어나갈 것인지 깊이 있게 고민해봐야겠다
  • 그래야 간결한 풀이가 나옴 (물론 이해하거나 생각하는데 시간은 많이 걸리지만…)