[코딩테스트 일지 - 99클럽] 2일차 - H Index
코딩 테스트 준비 일지 2 일차
문제
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회 이하입니다.
입출력 예
citations return [3, 0, 6, 1, 5] 3
입출력 예 설명
이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.
문제 풀이 접근
이 문제를 처음 접했을 때, 정확히 어떻게 접해야하는지, H Index가 무엇을 의미하는지 이해하지 못했다.
그저 아! 원소를 하나 찝어서 이 수 기준으로 이상 이하로 갯수 분리해서 비교하면 쉽게 풀리겠지! 가 맨 처음 접근이었다.
이 문제를 풀기 위해 해야할 접근 방법이 하나 있는데, 원소의 수는 인용된 수임을 잊어선 안된다.
문제를 풀다보니 맨 앞에 있는 3이 답이고, 이게 논문의 편수로 착각하고 문제를 풀었는데, 논문의 수와 인용된 수를 분리해서 생각해야한다.
문제를 풀기위한 플로우는 아래와 같다.
1. 오름차순으로 정렬한다.
2. 논문 수의 제한은 0 < n < 1000 이다.
3. 1000 까지 순회돌려서 H Index 뽑아내자.
1번의 오름차순으로 정렬한다 => H Index의 최댓값을 뽑기 위함이다.
2,3번의 논문수 제한 1000이라서 for문으로 1000까지 돌려서 H Index를 뽑았다.
작성 코드 ( C# )
using System;
public class Solution
{
public int solution(int[] citations)
{
int answer = 0;
Array.Sort(citations, (a, b) =>
{
return a.CompareTo(b);
});
for (int i = 0; i < 1000; i++)
{
int[] getReference = Array.FindAll(citations, rhs => rhs >= i);
int getRefCnt = getReference.Length;
int[] getBalance = Array.FindAll(citations, rhs => rhs < i);
int getBalanceCnt = getBalance.Length;
if (i <= getRefCnt && i >= getBalanceCnt)
{
answer = i;
}
}
return answer;
}
}다른 방식의 문제 풀이 원리
다른 방식의 문제 풀이는 이렇게 되는 방법도 있는 것 같다 .
origin 입력을 sort 처럼 오름차순으로 정렬한다.
index i 를 하나씩 픽해서 그 앞의 인덱스 갯수와 비교를 하면 i 원소의 기준 이상 이하가 분리가 된다.
이것으로 수 비교를 하여 H Index를 뽑아내는 방식도 있다.
코드 작성 ( C# )
public static int solution(int[] citations)
{
int hindex = 0;
Arrays.sort(citations);
for (int i = 0; i < citations.length; i++) {
if(citations[i] >= citations.length-i){
idx = citations.length-i;
break;
}
}
return hindex;
}참조 블로그
다른 방식의 문제풀이 및 코드 참조