[Programmers/sort] H-index

문제의 내용은 프로그래머스/정렬/H지수에서 확인할 수 있다.

이 문제는 사실상 국어 문제라고 봐도 무방하지 않을까싶었다. 우선 문제를 풀기 전에, H지수가 뭔지에 대해 정확하게 짚고 넘어가는게 중요하다. 이것은 H 지수에 대한 내용이다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

문제를 유출하면 법적인 책임을 물을 수 있다고 명시되어있지만, 위의 글은 위키 백과를 참고한 내용이라니까 상관 없겠지.

H지수에 대한 내용을 변수 h에 대해 정리하면 다음과 같다.

• n편의 논문이 있다.
  • 이 중에 h번 이상 인용된 논문은 h편 이상이다.
  • h편 이상 인용된 논문을 제외하고 남은 논문의 인용 횟수 중, 최대 인용 횟수는 h보다 작거나 같다.

위에 정리된 사항을 보면, H지수는 0보다 크거나 같고 논문의 갯수보다는 작다는 것을 알 수 있다.

function calcHIndex(논문) {
  for (h=논문의_갯수; h>0; h--) {
    let h번_이상_인용된_논문의_수 = 0;
    let 남은_논문의_인용_횟수_중_최대_인용_횟수 = 0;

    for(i=0; i<논문의_갯수; i++) {
      if(논문[i] >= h) {
        h번_이상_인용된_논문의_수++;
      } else if (논문[i] > 남은_논문의_인용_횟수_중_최대_인용_횟수){ // 논문[i] < h
        남은_논문의_인용_횟수_중_최대_인용_횟수++;
      }
    }

    if(h번_이상_인용된_논문의_수 >= h
      && 남은_논문의_인용_횟수_중_최대_인용_횟수 <= h) {
        return h;
      }
  }

  return 0; //H지수는 0이상 논문의 갯수 이하
}

주어진 조건에 따라서 수도코드를 작성하면 위와 같이 나온다. 이를 ES6의 화살표 함수와 컬렉션 함수들을 사용해서 구현하면 좀 더 간단하게 구현할 수 있다.

function solution(citations) {
  let result = 0;

  citations.forEach((e, index) => {
    let moreThanH = 0;
    let lessThanH = 0;
    const h = index+1;

    citations.forEach((e, index) => {
      if(e >= h) {
        moreThanH++;
      } else if (e > lessThanH) {
        lessThanH = e;
      }
    });

    if(moreThanH >= h && lessThanH <= h) {
      result = h;
    }
  });
  return result;
}

여기서 citations를 두 번 순회하게되므로, O(n²)의 시간복잡도가 소요됨을 알 수 있다. 좀 더 간단하게 해결할 수 있는 방법은 없을까?

solution(citations) {
  let h = 0;

  citations
    .sort((a, b) => b-a)
    .forEach((e, index) => {
      if(e>index) {
        h = (index+1);
      }
    }, h);

  return h;
}

Wikipedia: H-index의 Calculation항목을 살펴보자.

• First we order the values of f from the largest to the lowest value.
• Then, we look for the last position in which f is greater than or equal to the position (we call h this position).

우선 내림차순으로 값을 정렬한 뒤 순회를 한다. 이 때 index의 값이 index 이상인 경우, 이를 H-index라고 부른다고 되어있다. 따라서 주어진 배열 citations를 오름차순으로 정렬한 뒤, 배열을 순회하면서 배열의 값이 index보다 큰 경우를 찾아내면 된다.

이 때 주의할 점은, H-지수의 값은 0부터 시작되는 배열의 인덱스가 아니라 실제 숫자의 위치를 가리키는 (인덱스+1)의 값이라는 것 정도. 사실상 참고문서로 링크되어있는 Wikipedia에 계산식이 나와있으니, 잘 읽고 이해하기만 하면 되는 문제다.