H-Index

💡

Level 2 210921 https://programmers.co.kr/learn/courses/30/lessons/42747

과거 내 풀이

function solution(citations) {
    var answer = 0;
    // 0 1 3 5 6
    // 뺄셈 연산 함수를 인자로 넘겨 크기비교를 하여 리턴되는 값의 음수, 양수를 통해 위치를 판단하게 할
    citations.sort(function (f, s) {
        return f - s;
    });
    // n편 중 h번 이상 인용된 논문이 h편 이상 일때 h의 최댓값이 h-index
    var h;
    for (var i = 0; i < citations.length; i++) {
        // i일때 가장 큰 h값(논문 편수)
        h = citations.length - i;

        // 논문 인용횟수가 h 이상인지 확인
        if (citations[i] >= h) {
            answer = h;
            break;
        }
    }

    return answer;
}

문제 설명

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회 이하입니다.

입출력 예

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

My solution

h번 이상 인용된 것이 h가지 이상인 경우 h를 증가시킨다. 하지만 이 작업을 위해 매 인덱스마다 배열 전체를 탐색해서 확인해야 한다는 점이 성능상 불리하다.

3 0 6 1 5

0번 이상 인용 : 전부 성립

1번 이상 인용 : 3 6 1 5 (4가지)

2번 이상 인용 : 3 6 5 (3가지)

3번 이상 인용 : 3 6 5 (3가지) ...

따라서 citations 배열을 정렬해본다. 그래야 기준을 벗어났을 때 다음 값을 계산할 필요가 없어진다. [0, 1, 3, 5, 6] 이러한 배열이 되면 h값을 구하는 것은 훨씬 빨라진다.

예를 들어, 3번 인용된 논문이 있으면 그 값이 나타난 인덱스 뒤로는 반드시 3번 이상 인용된 논문만 존재할 것이므로 "배열의 길이에서 3번 인용된 논문의 인덱스를 빼주면" 3번 이상 인용된 논문의 총 개수를 구할 수 있음을 알 수 있다.

즉 for문 내에 임시 변수를 두고 "남은 논문 개수"를 설정하여 줄여가면서 그 개수가 최대가 되려면 인용 횟수가 남은 논문 개수와 같거나 커지는 순간 멈춰야한다.

배열에는 인용횟수가 오름차순으로 정렬되어 있고 남은 논문 개수는 반복할 때마다 1개씩 줄어들 것이기 때문에 남은 논문 개수를 기준으로 h 인덱스가 성립되는 순간 h를 리턴한다.

유의해야할 것은 if(h ≤ citations[i])) 의 조건문에 걸리지 않는 테스트케이스인데 아래처럼 [0]이나 [0,0,0]인 경우 h가 1이상이 들어가기 때문에 h값이 리턴되지 않으므로 answer를 0으로 할당해주면 된다.

소스 코드

function solution(citations) {
    let answer = 0;
    citations.sort((a, b) => a - b);

    for (let i = 0; i < citations.length; i++) {
        let h = citations.length - i;

        if (h <= citations[i]) return h; // 남은 인
    }

    return answer;
}

test("solution", () => {
    // expect(solution([3, 0, 6, 1, 5])).toBe(3);
    // expect(solution([88, 89])).toBe(2);
    // expect(solution([3])).toBe(1);
    // expect(solution([1])).toBe(1);
    expect(solution([0])).toBe(0);
    expect(solution([0, 0, 0])).toBe(0);
});