[코드리뷰] 프로그래머스

티스토리 뷰

프로그래밍/코드리뷰

donie 2020. 11. 3. 22:57

1. 문제

코딩테스트 연습 - H-Index

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

programmers.co.kr

2. 소스코드 (Python3)

def solution(citations):

citations = sorted(citations)

l = len(citations)

for i in range(l):

if citations[i] >= l-i:

return l-i

return 0

3. 고찰

1) 알고리즘

citations를 오름차순 정렬함.

인덱스를 가지고 for문을 돌리면서

citations[i] >= I-i인 경우, 즉 자신보다 큰 값이 h-1개 있는 경우

인덱스는 0부터 시작해서 헷갈린다.

i번째 인덱스는 (i+1)번째로 작은 citation 값이다. 이 값이 I-i보다 큰 경우

h = I-h이고, (i+1)번째로 작다는 것은 I-h+1 = I-(h-1)번째로 작다, h-1번째로 크다, 자신보다 큰 값이 h-1개 있다.

I-i를 리턴한다. 즉 h를 리턴하는 것.

2) 시간복잡도

sorted함수의 시간복잡도는 O(N log N)

citations멤버만큼 for문을 돌리기 때문에 O(N)

즉, 이 코드의 시간복잡도는 O(N log N)이다.

[코드리뷰] 프로그래머스 - 주사위 게임 (product함수, sum함수, int함수) (0)	2020.12.06
[코드리뷰] 프로그래머스 - 세 소수의 합 (루트, combinations 함수, count 함수) (0)	2020.12.06
[코드리뷰]프로그래머스_카펫 (0)	2020.10.30
[코드리뷰] 프로그래머스_더 맵게 (0)	2020.10.03
[코드리뷰]프로그래머스_다리를 건너는 트럭 (0)	2020.10.03

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함