[프로그래머스, C++] H-Index(정렬 파트)

문제 링크

코딩테스트 연습 - H-Index

 

 

 

풀이

문제 이해하기 힘들면 위키백과 보기를 추천합니다.(제가 그럼...)

 

생각해보면, h-index를 한정 짓는 것은 논문을 편찬한 개수이다.

따라서 인용된 횟수랑 비교하면서 논문을 편찬한 개수를 줄여나가면서 h-index의 최대를 구할 수 있다.

 

따라서 코드를 요약하자면,

 

citations을 오름차순으로 정렬하여 원소값과 비교하면서 순회한다.(인용된 횟수랑 비교하기 위해서)

i 번째 원소(논문 인용횟수) 이상인 원소(논문) 갯수는 citations.size()-i 개이므로 answer에 미리 할당한다.(반복문의 3번 이유로)

 

반복문 순회하면서

{

    1. i 번째 원소값과 answer가 일치할 경우 break;

    2. i 번째 원소값이 answer(i번째 원소 이상인 원소 갯수)보다 클 경우 break;

    3. 둘다 아닐 경우 answer--; (citations.size()-i)와 같다.

}

 

 

 

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

using namespace std;

// 과학자가 발표한 논문 n편 중 h번 이상 인용된 논문이 h편이상, 나머지 논문 h번 이하 인용될 경우
// h의 최댓값은 H-Index이다.

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