[Level 2] H-Index - 정렬 | C++

[문제]

함수의 인자로 논문의 인용 횟수가 담긴 배열이 주어지는데, 여기서 H-index를 구해 반환하는 것이 문제이다. H-Index란 주어진 논문들 중 인용 횟수가 h번 이상인 논문이 h개 이상 존재하고, 나머지 논문은 h번 이하 인용된 것 중 가장 큰 h 값을 말한다.

말이 좀 어려운데 쉽게 설명해서 배열 [0, 0, 3, 6, 8, 10]이 주어졌다면, 6편의 논문들 중 h 이상의 값을 가지고 그것들이 h편 이상이면 된다. h가 0이라면 0 이상의 값을 0편 이상 가지고 있으므로 만족한다. 1이여도 만족하고 2여도 만족하고 3이여도 만족한다. 4는 4보다 크거나 같은 값이 3개밖에 없으므로 만족하지 않는다. 따라서 0,1,2,3 중 가장 큰 3이 H-Index가 된다.

[풀이]
내 풀이 방법은 간단하다. 우선 주어진 배열을 오름차순으로 정렬한다. 문제의 예제로 예를 들면 다음과 같이 된다.

0 1 3 5 6

H-Index는 배열의 크기를 넘을 수 없으므로 최댓값을 찾기 위해 배열의 크기부터 1씩 줄여가며 차례대로 확인한다.

배열	0	1	3	5	6
H-Index	5	4	3	2	1
Index	0	1	2	3	4

위 배열의 크기는 5이므로 5부터 시작하여 각 요소와 차례대로 비교한다. 만약 배열의 요소 중 H-Index보다 크거나 같아지는 순간을 찾았다면, 해당 위치로부터 남은 요소들의 수가 H-Index보다 크거나 같은지 체크한다. 위 배열은 요소가 3일 때 H-Index(3)보다 크거나 같아진다. 또한 해당 위치부터 남아있는 요소의 개수는 3,5,6 3개로 H-Index 보다 크거나 같다. 이 개수는 배열의 크기 5에서 현재 인덱스인 2를 빼면 나온다. 그리고 H-Index는 큰 값부터 시작했으므로 최초로 만족하는 값이 최댓값이 맞다. 그리고 위 표를 보면 H-Index는 1까지 밖에 확인하지 못한다. 따라서 H-Index가 0일 경우는 밑에서 설명한다. 

 

[코드]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) 
{
    sort(citations.begin(), citations.end());
    
    size_t size = citations.size();
    uint32_t h = size;
    for(size_t i = 0; i < size; ++i)
    {
        if((citations[i] >= h) && (size - i >= h))
        {
            return h;
        }
        --h;
    }
    
    return 0;
}

만약 위 루프에서 답을 구하지 못한다면 0을 반환한다. 예를 들어 [0, 0, 0, 3]인 경우 H-Index는 0인데, 아까 설명했듯이 1까지만 검사하므로 위 루프를 탈출한다면 0이 답이 된다. std::sort 함수가 N*logN의 시간 복잡도를 가지므로 위 코드의 시간 복잡도는 O(N*logN)이다.