[정렬, 난이도 하] 프로그래머즈, H-Index

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이라고 했을 때 가능한 h의 최댓값을 구하는 문제이다.

단순히 citations를 오름차순으로 정렬하면 문제를 쉽게 해결할 수 있다.

오름차순으로 정렬한 후에 n-h번째에 있는 논문의 인용 수가 h이상이라는 뜻은, 논문의 인용수가 h이상인 논문의 수는 h개 이상이라는 뜻이 된다.

본인의 소스코드에서 사용한 정렬은 시간 복잡도가 O(nlogn) 이므로, 시간복잡도도 O(nlogn) 밖에 되지 않는다.

 

테스트케이스 16개 모두 통과

 

 

#include <vector>
#include <algorithm>
int maxi(int a,int b){
    if(a>b) return a;
    else return b;
}
using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(),citations.end());
    int answer = 0;
    for(int i=1;i<=citations.size();i++){
        if(citations[citations.size()-i]>=i) {
            answer = maxi(answer,i);
        }
    }
    return answer;
}