[C++] 프로그래머스 - "H-index" 풀이

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과에 따르면, H-Index는 다음과 같이 구합니다.

 

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

 

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

문제 주소: https://programmers.co.kr/learn/courses/30/lessons/42747

 

 

문제 풀이

위키백과에 나오는 H-index의 계산 방법은 다음과 같다. 

 

출처: https://en.wikipedia.org/wiki/H-index

논문의 인용 횟수를 내림차순으로 정렬했을 때, (index + 1) <= citations[i]을 만족하는 최대 index + 1이 H-index이다. 이때 index + 1은 citations[i]번 이상 인용한 논문의 개수를 의미한다. 

 

예시를 들어 설명하자면

citations = [3, 0, 6, 1, 5]일 경우, 이를 내림차순으로 정렬하면 [6, 5, 3, 1, 0]이다. 

• 6번 이상 인용된 논문의 수: 1개  // 1 <= 6

• 5번 이상 인용된 논문의 수: 2개  // 2 <= 5

• 4번 이상 인용된 논문의 수: 3개  // 3 <= 4

• 3번 이상 인용된 논문의 수: 4개   // 4 > 3 이므로 위의 조건 불만족

이 예시에서 (index + 1) <= citations[i]를 만족하는 (index + 1)은 [1, 2, 3]이고, 이 중 최댓값인 3이 H-index가 된다. 

 

 

예시2) citations = [100, 50, 10]일 경우

• 100번 이상 인용된 논문의 수: 1개

• 50번 이상 인용된 논문의 수: 2개

• 10번 이상 인용된 논문의 수: 3개

이 예시에서 (index + 1) <= citations[i]를 만족하는 (index + 1)은 [1, 2, 3]이고, 이 중 최댓값인3이 H-index가 된다. 

 

 

소스 코드

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.begin(), citations.end(), greater<int>()); // citations를 내림차순 정렬
 
    for (int i = 0; i < citations.size(); i++) {
        if (i + 1 <= citations[i]) // (i + 1)은 citations[i]번 이상 인용된 논문의 수
            answer = i + 1;
        else
            break;
    }
    
    return answer;
}