[알고리즘] H-index

문제설명

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 → 논문의 수
1번 논문 3회 v
2번 논문 0회
3번 논문 6회 v
4번 논문 1회
5번 논문 5회 v
→ 3회 이상 인용된 논문은 3개(1,3,5)

맨처음에는 위와 같이 이해를 했다.
그래서 주어진 논문의 수를 반으로 나눠서 기준점을 잡으면 될까했는데 접근방식이 틀렸다.
테스트 케이스가 몇개는 맞고, 틀리고를 반복하다가 나중에는 올 실패를 보게 되어서 다른 사람들이 고민하는 부분들을 읽어봤다. 문제 이해부분은 다 비슷비슷한가보다ㅋㅋ

그중 기타참조를 참조해서 다시 알고리즘을 짰다.

1.전체 논문을 많이 인용된 순으로 정렬한다.
2.인용된 횟수가 논문 수와 같거나, 논문 수보다 작으면 그 숫자가 H-index가 된다

---

이해하는 부분이 잘못된 것 같아서 참조문서대로 위키백과(영문)에 나온 알고리즘 그대로 작성했다.

1. 내림차순 정렬을 진행한다.
2. f의 값이 그 위치보다 크거나 같은 곳의 마지막 위치 = h-index

// 변수로 h-index의 값을 두어 증가시켜주거나
// 6 > 0 + 
// 5 > 1 +
// 3 > 2 +
// 1 → 3 x
// 0 → 4 x

// 위치 갱신을 위해 maxH를 둘 수 있다.
6 > 1  
5 > 2 
3 = 3 → 마지막 위치
1 → 4 
0 → 5 

5 > 1
5 > 2
5 > 3
5 > 4 → 마지막 위치

구현

최종

// hidx를 증가시켜서 구하는 경우
function solution(citations) {

  citations.sort((a,b) => b-a);

  let hidx = 0;
  for(let i = 0; i < citations.length; i++){
    if(citations[i] > i){
        hidx++;
    }
  }
  return hidx;
}
// maxH를 갱신시키는 경우
function solution(citations) {

  citations.sort((a,b) => b-a);
  let maxH = 0;
  for(let i = 0; i < citations.length; i++){
    if(citations[i] >= i+1){
        maxH = i+1;
    }
  }
    return maxH;
}
// forEach로 리팩토링
function solution(citations) {
    
    citations.sort((a,b) => b-a)
    let maxH = 0;

    citations.forEach((ele, idx) => {
       if(ele >= idx+1) {
           maxH = idx+1;
       } 
    });
    
    return maxH;
}
// filter로 리팩토링
function solution(citations) {
    
   citations.sort((a,b) => b-a)   
   return citations.filter((ele, idx) => ele >= idx+1).length;
    
}

---

//while문
function solution(citations) {
let sortPapers = citations.sort((a,b) => b-a);
let count = 0;
while(count <= sortPapers.length){
    if(count+1 <= sortPapers[count]){
        count++;
    } else break;
}
    return count;
}
// for문
function solution(citations) {
  let sortPapers = citations.sort((a,b) => b-a);
  let count = 0;
  for(let i=0; i < citations.length; i++){
      if (i+1 <= citations[i]){
          count++;
      }
      else break;
  }
    return count;
}

다른 사람 풀이

관점은 다르지만 위의 참조한 링크와 유사한 풀이들이 많았다.

• max 값을 이용한 방법(최댓값을 이용한 방법)

function solution(citations) {
 // 발표한 논문 수(n) 보다 많은 인용횟수(h)를 가진 논문 수(maxH)
 //발표한 논문 수와 각 논문의 인용횟수를 비교한다.
 for(let n = citations.length; n >= 0; n--){
   let maxH = citations.filter((h) => h >= n).length;
   // 발표한 논문 수와 높은 인용횟수를 가진 논문수를 비교한다.
   if(maxH >= n) return n;
 }
}

위키-H지수