설명

프로그래머스의 H-Index 문제다.

좀 특이한 개념인데 어떤 사람의 논문이 여러 개 있을 때 H번 이상 인용된 논문이 H개 이상 있다면 이를 그 사람의 H-Index로 나타낸다는 것이다. 문제에서는 배열로 각 논문의 인용 횟수가 주어지며 이를 기반으로 최대 H-Index를 계산해야 한다.

예를 들어 논문이 총 다섯 개가 있으며 [3, 0, 6, 1, 5]번 인용되었을 때 이 저자의 H-Index는 3이다. 왜냐면 3번 이상 인용된 논문이 3개 이상(3, 6, 5) 있기 때문이다. 4번 이상 인용된 논문은 2개 밖에 없기 때문에 해당되지 않는다.

풀이

문제에서는 논문의 인용 횟수를 0번에서 10,000번 사이로 제한하고 있으며 논문의 갯수는 1편 이상 1,000편 이하로 제한된다.

직관적으로 생각할 수 있는 풀이는 0부터 10,000까지, 즉 최대 인용 횟수까지 반복하며 모든 논문의 인용 횟수를 비교, H번 이상 인용된 논문이 H개 이상인 지 확인하는 방법이다. 하지만 이 방법은 너무 원시적이고 비효율적이다. 그러면 어떻게 개선할 수 있을까?

이 H-Index의 핵심은 막대 그래프로 나타내보면 더 잘 이해할 수 있다.
위의 예시인 [3, 0, 6, 1, 2]를 막대 그래프로 나타낸 것이다. H-Index가 왜 3인지 더 쉽게 이해할 수 있다. 그렇다면 이 막대 그래프를 정렬한다면 특정 높이(인용 횟수) 이상의 막대(논문)가 몇 개 있는지 더 빠르게 알 수 있지 않을까?
만약 막대가 정렬되었다면 높이 N의 막대에서는 자신보다 뒤에 있는 막대, 즉 논문들이 전부 N번 이상 인용되었다고 확신할 수 있다. 이 경우 뒤에 있는 막대들을 일일히 조회해서 N번 이상 인용되었는지 확인할 필요가 없기 때문에 탐색 시간을 획기적으로 줄일 수 있다.

즉 문제 풀이의 핵심은 논문의 인용 횟수를 정렬하고 처음 논문부터 하나씩 비교하면서 H-Index를 증가시키는 것이다. 이를 기반으로 작성한 코드는 다음과 같다.

import java.util.*;


class Solution {
    public int solution(int[] citations) {
        // 논문들의 인용 횟수를 정렬.
        Arrays.sort(citations);
        int hIndex = 0;
        // 모든 논문 인용 횟수를 탐색하며 H-Index를 계산.
        for(int citationIndex=0; citationIndex<citations.length; citationIndex++) {
            // 현재 논문 인용 횟수가 H-Index 이상이고
            // 현재 논문을 포함한 이후의 모든 논문들,
            // 즉 인용 횟수가 H-Index 이상인 논문들이 H-Index 개 이상 있다면
            // H-Index를 증가.
            while(
                citations[citationIndex] >= hIndex &&
                citations.length - citationIndex >= hIndex) {
                hIndex++;
            }
            // H-Index는 while 반복문에 의해 조건을 만족하지 않을 때까지 증가.
        }
        
        // 그렇기 때문에 마지막에 반환 시 1을 차감해서 반환.
        return hIndex - 1;
    }
}

현재 논문의 인용 횟수가 H-Index 이상인지 계속 확인하고 있기 때문에 H-Index가 과도하게 증가하는 것을 막을 수 있었다. 아마 다른 풀이에서는 중복된 논문의 인용 횟수를 건너뛰는 로직도 구현하고 그랬던 것 같은데 여기서는 정렬 및 간단한 계산을 통해 그런 과정을 생략할 수 있었다.

후기

H-Index라는 개념 자체가 좀 헷갈렸기 때문에 예제를 계속 확인해본 것 같다. 요소들을 정렬하는 것이 핵심인 것 같다.