Contents
- 문제 설명
[제한사항]
[입출력 예] - 알고리즘 분석
[나의 풀이]
문제 설명
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
- 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
입출력 예
citations | return |
[3, 0, 6, 1, 5] | 3 |
알고리즘 분석
- 나의 풀이
def solution(cit):
cit.sort() # 숫자를 작은 순서로 정렬
for idx, c in enumerate(cit): # index와 요소의 값
if c >= len(cit[idx:]): # cit의 요소가 cit[idx:]보다 크거나 같을 경우
return len(cit[idx:]) # h-index를 반환
return 0
지문에서 h-index에 대해 요구하는 조건은 다음과 같다.
- 모든 논문 n 편 중,
- h번 이상 인용된 논문이 h편 이상
- 나머지 논문이 h번 이하 인용
- h의 최댓값이 H-index
이 조건을 처음 봤을 때는 h가 3번 들어가서 뭐가 뭔지 헷갈렸었다.
그래서 다음과 같이 쉽게 풀어보았다.
우선 "cit = [2, 5, 4, 10, 30, 9, 11, 7]"라고 가정해보자.
1. h번 이상 인용된 논문이 h편 이상
h의 값은 무조건 "len(cit)"보다 작다는 것을 의미한다.
위의 cit의 최댓값은 30이다. 그것을 h에 대입해보면
- 30번 이상 인용된 논문이 30편 이상 : 여기서 "논문"의 수는 "cit"의 길이와 같다. 그렇다는 말은 h가 len(cit) 보다 큰 경우는 절대 없다는 의미다. 즉, h의 범위는 0부터 len(cit)까지이므로 논문이 30편 이상일 경우는 절대 없다.
그리고 착각할 수 있는 부분이 있는데,
난 처음에 cit의 요소만 h가 될 수 있는줄 알았지만 h는 0부터 len(cit) 사이의 정수이기만 하면 된다.
2. 나머지 논문이 h번 이하 인용
이 부분은 지문을 어렵게하는 함정인 것 같다.
h번 이상 인용한 논문을 전부 구했을 경우, 나머지 논문은 필연적으로 h번 이하로 인용된다.
즉, 이 부분은 신경쓰지 않아도 상관없다.
3. if c >= len(cit[idx:])
위처럼 비교하는 이유를 "cit = [2, 5, 4, 10, 30, 9, 11, 7]"로 설명하자면
C | 부호 | len(cit[idx:]) = h | 참 or 거짓 | 해석 |
2 | >= | 8 | False | 2이상인 요소가 8개 |
4 | >= | 7 | False | 4이상인 요소가 7개 |
5 | >= | 6 | False | 5이상인 요소가 6개 |
7 | >= | 5 | True | 7이상인 요소가 5개 |
위의 표에서 C는 cit의 요소, len(cit[idx:])는 C이상인 요소의 개수를 나타낸다.
지문에 따르자면 C는 "논문이 인용된 횟수", len(cit[idx:])는 "C 이상 인용된 논문의 개수"이다.
위의 표에서 len(cit[idx:])의 값을 보면 알겠지만 h-index가 가질 수 있는 최댓값부터 시작해서 1씩 줄어들고 있다.
그리고 C가 len(cit[idx:])보다 커지면 True를 리턴하고 결과적으로 len(cit[idx:])를 h의 최댓값으로 리턴한다.
최종적으로 h-index는 5가 된다.
아직 이해가 안 된다면
h =5일 경우와 h = 7일 경우를 비교해보면 된다.
- h = 5일 경우 : (요구조건) 5 이상인 요소가 5개 이상 : (조건 만족) 5 이상인 요소가 6개
- h = 7일 경우 : (요구조건) 7 이상인 요소가 7개 이상 : (조건 불만족) 7 이상인 요소가 5개
위에서 확인한 것처럼 5 이상인 요소가 5개 이상일 경우에 h가 될 수 있는데
우리는 반복문을 거치며 이미 조건이 만족하는 것을 확인했다.
만약 C의 값 중에 h가 없더라도 요구조건을 만족하는 가장 큰 h-index 값을 얻을 수 있다.
마치며....
솔직히 이런 문제는 금방 풀 수 있을 줄 알았는데
누가 만들었는지는 몰라도 은근히 골머리를 앓게 만든 문제였다.
'프로그래머스(Python) > Level2' 카테고리의 다른 글
[프로그래머스] '위장' 알고리즘 풀이 - Python (0) | 2020.10.20 |
---|---|
[프로그래머스] '구명보트' 알고리즘 풀이 - Python (0) | 2020.10.20 |
[프로그래머스] '전화번호 목록' 알고리즘 풀이 - Python (0) | 2020.10.19 |
[프로그래머스] '큰 수 만들기' 알고리즘 풀이 - Python (0) | 2020.10.19 |
[프로그래머스] '소수 찾기' 알고리즘 풀이 - Python (0) | 2020.10.19 |