프로그래머스 - H-Index

1. 문제

문제 링크

2. 풀이

일단 H-Index의 정의부터 다시 살펴봅시다.

n편의 논문중, h번 이상 인용된 논문이 h편 이상, 나머지 논문은 h번 이하로 인용되었을 때 h의 최대값.

그렇다면 citations배열을 내림차순 정렬했을 때
특정 H-index값을 기준으로
왼쪽 요소들은 h보다 크거나 같고,
오른쪽 요소들은 h보다 작거나 같다는 사실을 유추할 수 있습니다.

예를 들어 논문들이 아래와 같이 존재할 때

[8, 7, 7, 6, 6, 1] - 논문들
[0  1  2  3  4  5] - 논문의 인덱스

H-index인 5번 index에 대해서
왼쪽 요소들 [8, 7, 7, 6, 6]은 5보다 크거나 같고
오른쪽 요소들 [1]은 5보다 작거나 같습니다.

그렇다면 정답인 H-index를 구하는 방법은
위에서 찾은 규칙을 만족하면서
왼쪽에 있는 요소의 개수가 h개 이상 있는 지점을 찾는 겁니다.

[8, 7, 7, 6, 6, 1] - 논문들
[0  1  2  3  4  5] - 논문의 인덱스

인덱스가 0일 때 - 8번 이상 인용된 논문의 개수는 1개, (8 < 1) == false 넘어감
인덱스가 1일 때 - 7번 이상 인용된 논문의 개수는 2개, (7 < 2) == false 넘어감
...
인덱스가 4일 때 - 6번 이상 인용된 논문의 개수는 5개, (6 < 5) == false 넘어감
인덱스가 5일 때 - 1번 이상 인용된 논문의 개수는 6개, (1 < 6) == true 정답은 5

코드로 구현하면
const hIndex = citations.sort((a, b) => b - a).findIndex((v, i) => v < i + 1);
이렇게 표현할 수 있습니다.

1. 내림차순으로 정렬
2. 왼쪽에 있는 요소의 개수가 현재 요소의 값(인용 횟수)보다 클 때의 인덱스

하지만 여기서 끝이 아닙니다.
이런 예제가 들어오면 어떻게 될까요?
[5, 5, 5, 5]

마지막 인덱스를 기점으로 생각해봐도
5(인용 횟수) < 4(마지막 인덱스 + 1) == false이기 때문에 -1을 반환하게 되어 틀린 답이 됩니다.
당연히 상식적으로 생각해봤을 때 제일 적은 인용 횟수 5보다 n(논문의 개수)이 작기 때문이지요.

이 때는 n(논문의 개수)이 정답이 됩니다.
역시 상식적으로 생각해봤을 때 4(논문의 개수)에 대해서 모든 논문들이 4번 이상 인용 되었고
나머지 4번 이하 인용된 논문들은 0개이기 때문에
나머지 0개의 논문들에 대해 4번 이하로 인용됐는지 확인할 필요도 없기 때문입니다.

즉, 중요한 조건은 h번 이상 인용된 논문이 h개 이상인가? 입니다.

3. 전체 코드

function solution(citations) {
    const hIndex = citations.sort((a, b) => b - a).findIndex((v, i) => v < i + 1);
    return hIndex == -1 ? citations.length : hIndex;
}