문제

Programmers, H-Index

핵심

• 입력의 크기가 $10^3$이라 구현에 초점을 맞춘다.
• H-index를 구하는 문제이다. H-Index란 어떤 과학자가 발표한 논문 중에서, 해당 논문이 받은 인용 횟수가 논문의 수와 같거나 많은 최댓값이다. 예시에서 논문의 수와 인용 횟수가 주어진다. H-index는 자료에서 주어진 인용 횟수로 구할 수 있다고 생각하여, 모든 인용 횟수를 탐색하면서 논문의 개수와 같을 때 H-Index를 갱신하는 방법으로 구했다.
• H-Index를 구하는 다음의 조건식을 작성 할 때 h번 이상 인용된 논문이 h편 이상
  직관적으로 오른쪽처럼 조건식을 작성할 수 있는데 if (cnt >= h) hIndex = cnt 인용이 가능한 최대 논문 갯수를 알고 싶다면 아래처럼 구하는 것이 정확한 H-Index 정의에 부합한다. if (cnt <= h)

개선

• 아래의 C++ 코드는 조금 더 개선할 여지가 있다. 인용횟수가 오름차순으로 정렬될 때 가장 적은 인용횟수에 해당하는 논문의 개수는 예시를 기준으로 5개가 가능하다. 즉 인용 횟수 배열의 인덱스가 하나 증가할 때마다 논문의 개수는 하나씩 줄어든다. 조건을 만족한다면 해당 값이 최댓값이므로 불필요한 반복을 하지 않아도 된다. 개선한 코드는 Java로 작성하였다.

코드

시간복잡도

• $O(N^2, Nlog_2N)$

C++

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(vector<int> citations) {
    int hIndex = 0;
    for (int i = 0; i < citations.size(); ++i) {
        int h = citations[i];
        int cnt = 0;
        for (int j = 0; j < citations.size(); ++j) {
            if (citations[j] >= h)
                ++cnt;
        }
        if (cnt <= h)
            hIndex = max(hIndex, cnt);
    }
    return hIndex;
}

Java

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        for (int i = 0; i < citations.length; ++i) {
            int cnt = citations.length - i;
            if (citations[i] >= cnt) {
                answer = cnt;
                break;
            }
        }
        return answer;
    }
}