프로그래머스(정렬; H-Index) c++

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

using namespace std;

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

 

해설:

h-index라는 가정으로 인용수가 h라고 가정했는데 인용된 논문 수와 h가 적절하게 똑같아야 한다.

먼저 내림차순으로 정렬해야한다. #include<algorithm>을 추가해주고 citations을 sort()를 이용하영 정렬하며 greater<int>를 이용하여 내림차순으로 정렬한다.  이유는 다음과 같다.

 

• 1번째 논문: 인용 6번 → 1 ≤ 6 ✓
• 2번째 논문: 인용 5번 → 2 ≤ 5 ✓
• 3번째 논문: 인용 3번 → 3 ≤ 3 ✓ (여기가 마지막으로 성립하는 지점)
• 4번째 논문: 인용 1번 → 4 ≤ 1 ✗ (여기서 깨짐)

이런식으로 인용들은 높은 수부터 내려오고 index는 1씩 증가 시켜서 비교를 진행하면 정확히 중앙에 마주하기때문에 가장 빠른 방법이라고 볼 수 있다.

그렇게 인용수가 i보다 크면 h를 증가 시키고 그 범위를 벗어나면 h는 그 값에서 변화되지 않는다.