프로그래머스_H-Index

1. 문제

출처 : 프로그래머스

2. 소스코드

def solution(citations):     h=len(citations)     while h:         higher = 0         lower = 0         for c in citations:             if c>=h: higher += 1             else: lower += 1         if higher>=h and:             return h         h-=1         return h

 

3. 고찰

1) 알고리즘

n편 중 h편이기 때문에 h의 초기값을 len(citations)로 설정했다. 최대값을 찾는 문제이므로 위에서부터 내려가며 h값을 찾았다.

while loop를 돌면서

    h번 이상 인용된 논문 개수는 higher에,

    나머지 논문 개수는 lower에 세었다.

    higher개수가 h편 이상이면 h를 리턴하였다.

    h에 -1 해주었다.

 

2) 시간복잡도

입력 리스트 citations의 길이를 N이라 할 때,

while문은 N번 돌고

while문안에서 for문이 N번 돌기 때문에

시간복잡도는 O(N^2)이다.