프로그래머스 정렬 H-Index

문제 설명

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

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

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

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citations	return
[3, 0, 6, 1, 5]	3

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

---

나의 코드

이번 문제는 문제 이해가 어려웠다.

Index 번호	0	1	2	3	4
citations	3	0	6	1	5

이를 정렬하면

h에 대한 설명

index를 하나 정하고 해당 index에 해당하는 citations가 h보다 크거나 같고 해당 index를 포함하여 오른쪽에 있는 index의 개수가 h보다 크다면 답이 될 가능성이 있는 수이다.

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

using namespace std;

int solution(vector<int> citations) {
    int size = citations.size() - 1;
    int h = 1;
    int answer = 0;
    sort(citations.begin(), citations.end());
    if (citations[size] == 0) return 0;
    while (citations[size] >= h && size > 0) {
        if (citations[size - 1] > h) {
            h++;
            size--;
        }
        else break;
    }
    answer = h;
    return answer;
}

주석 있는 버전

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

using namespace std;

int solution(vector<int> citations) {
    int size = citations.size() - 1; //index
    int h = 1; //return 할 h
    int answer = 0; 
    sort(citations.begin(), citations.end()); //정렬
    if (citations[size] == 0) return 0; //모든 수가 0일 경우
    while (citations[size] >= h && size > 0) { //문제가 원하는 수가 될때까지
        if (citations[size - 1] > h) {
            h++;
            size--;
        }
        else break;
    }
    answer = h;
    return answer;
}

---

다른 풀이

 

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

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());

    for (int i = 0; i < citations.size(); ++i) {
        if (citations[i] < i + 1) {
            return i;
        }
    }

    return citations.size();
}

 Junghyun Kim , 김민규 , 강신욱 , - , 권오승 외 8 명의 풀이입니다.

 

나는 뒤에서 부터 citations을 보았는데 해당 풀이에서는 내림차순으로 정렬하여 앞에서부터 숫자를 찾았다.

그 외에는 기본적인 풀이방법은 동일한 것 같다.