티스토리 뷰
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.
과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
예를 들어서 입력이 [3, 0, 6, 1, 5] 면 3회 이상 인용된 논문이 3편 있다. 4회 이상 인용된 논문은 4편 이상이 안 되므로 H-Index는 3이다.
생각한 아이디어는 먼저 정렬을 한 다음,
[0, 1, 3, 5, 6]
각 원소를 보면서 남은 원소 개수랑 비교하는 것이다. 오름차순으로 정렬했으므로 내 뒤에 있는 논문들은 다 나보다 인용횟수가 많을 것이다.
예를 들어,
i = 0: 0이니까 패스
i = 1: 원소값이 1이다. 자신을 포함해서 뒤에 남은 원소 개수가 1보다 많으므로 1은 H-Index가 될 수 있다. H-Index 값을 1로 업데이트해준다.
i = 2: 원소값이 3이다. 자신 포함 뒤에 (즉, 3회 이상 인용된 논문이) 3편이 있으므로 3은 H-Index가 될 수 있다.
i = 3: 원소값이 5다. 자신 포함 뒤에 2편밖에 없으므로 5는 H-Index가 될 수 없다. 정렬이 되어있으므로 그 뒤도 뻔하니까 여기서 반복문을 빠져나온다.
처음 짠 코드:
def solution(citations):
h_ind = 0;
n = len(citations);
citations.sort();
for i in range(n):
if citations[i] <= n-i:
h_ind = citations[i];
else:
break;
return h_ind;근데 돌려보니 몇 개는 맞았지만 대부분 틀렸다. 생각나는 테스트케이스를 몇 개 넣어봤는데 다 맞다고 나와서 뭐가 문제지... 싶어서 질문 게시판을 봤다. 여기서 힌트를 얻었는데...
"[42, 22] 를 넣으면 답은 2다"
그렇다... 이 예시를 보면 두 논문 모두 2회 이상 인용이 됐으니 H-Index=2는 충족된다. 하지만 3 이상은 될 수 없다. 두 논문 모두 3회 이상 인용됐지만, 논문이 두편밖에 없기 때문이다.
즉 citations에 존재하지 않는 값이라도 답이 될 수 있었다. 문제 자체에 대한 이해가 한참 부족했던 것이었다.
그럼 이 반례를 어떻게 처리해줄까? 다행히 생각하는 데 오래 걸리진 않았다. 남은 논문 수보다 높은 값이 튀어나왔다는 얘기는 곧 남은 논문들의 편수가 지금 보고있는 논문의 인용수보다 적다는 얘기고, 그 말은 지금 보고있는 논문의 인용수가 H-Index가 될 수 없다는 의미다. 그렇다면? 이전의 값을 H-Index로 확정하거나, 혹은 남은 논문 편수가 더 많다면 그 값이 H-Index가 될 수 있다.
수정한 코드:
def solution(citations):
h_ind = 0;
n = len(citations);
citations.sort();
for i in range(n):
if citations[i] <= n-i:
h_ind = citations[i];
else:
if n-i > h_ind:
h_ind = n-i;
break;
return h_ind;별건 없고 남은 논문 편수가 더 많은 경우를 처리해주기 위한 if문 하나가 더 들어갔다.
근데 여기서 if를 제거하고 그냥 h_ind = n-i; 만 남겨놔도 채점에서 100점이 뜨더라. 이렇게 하면 당장 위의 [0, 1, 3, 5, 6] 부터 반례가 되는데, 5를 만났을 때 else로 빠진 다음 남은 논문 수 (2) 로 h_ind 값이 바뀌어버리기 때문이다 (답은 3). 채점에 쓰이는 테스트 케이스가 충분하지 않은 것 같고... 이걸 발견하구 나니까 이게 정말 확실한 정답인지도 의문이 든다. (...)