사용자 도구

사이트 도구


ps:problems:programmers:42747

H-Index

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42747
출처프로그래머스
문제 번호42747
문제명H-Index
레벨Level 2
분류

애드혹

시간복잡도O(nlogn)
인풋사이즈n<1000
사용한 언어Python
해결날짜2021/05/28
태그

고득점 Kit - 정렬

풀이

  • 배열을 인용횟수가 감소하는 순서대로 정렬을 해놓으면, 어떤 논문의 {배열내 index값} = {그 논문보다 인용횟수가 많거나 같은 논문의 갯수} 가 된다.
  • 따라서, 어떤 논문의 인용횟수가 h값이 될수 있는지를 찾기 위해, {그 논문보다 인용횟수가 많거나 같은 논문의 갯수} 와 {인용횟수}를 비교하는 것을 그냥 index과 인용횟수를 비교하는 것으로 끝.
  • 정렬에 걸리는 O(nlogn), h값이 될수 있는 후보들을 찾고 그중에서 max값을 구하기 위해서 한번씩 쭉 scan하는 과정에서 걸리는 O(n)을 합치면, 총 시간복잡도는 O(nlogn)

코드

"""Solution code for "Programmers 42747. H-Index".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42747
- Solution link: http://www.teferi.net/ps/problems/programmers/42747
"""


def solution(citations):    
    citations.sort(reverse=True)
    return max((h for h, cit in enumerate(citations, start=1) if cit >= h),
               default=0)

토론

댓글을 입력하세요:
E L K X K
 
ps/problems/programmers/42747.txt · 마지막으로 수정됨: 2021/05/28 04:49 저자 teferi