프로그래머스 - H-Index

프로그래머스 - H-Index

해당 문제는 H-Index를 구하는 문제이다. 논문과 관련된 수치로 그 학술자의 영향력을 판단하는 수치라고한다. 사실 문제가 잘 이해가 안되서 좀 자세히 몇 번을 읽어봤다.

문제 자체를 어렵지않았다. 우선 내림차순으로 논문 인용횟수를 정렬하였다. 그리고 첫번째 값을 Max값으로 잡고 그 값을 H-Index로 가정하고 H-Index가 될 수 있는지 점검한 뒤, 부합하면 그 값을 리턴, 아닐 경우 -1을 하여 다시 같은 로직을 수행하였다.

처음에는 주어진 배열 내에서만 H-Index를 찾으면 되지 않을까 싶었지만 [0, 6, 1, 5]와 같은 반례가 있을 것 같았다. 해당 배열에서도 배열 내에서만 H-Index를 찾으면 1이 나오지만, 사실 2가 나와야한다. 따라서 가장 큰 값에서 -1씩 하나씩 찾아봐야했다. 배열의 길이와 인용횟수의 최댓값이 그리 크지 않아서 충분히 시간복잡도가 좀 있어도 해결할 수 있을 것이라 판단했고, 잘 해결된 문제였다.

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

using namespace std;

bool compare(int a, int b) {
    return a > b;
}

int solution(vector<int> citations) {
    int answer = 0;

    sort(citations.begin(), citations.end(), compare);

    int maxNum = citations[0];

    while (maxNum > 0) {
        int more = 0;
        for (auto el : citations) {
            if (maxNum <= el) {
                more++;
            }
            else 
                break;
        }
        if (more >= maxNum) {
            answer = maxNum;
            break;
        }
        maxNum--;
    }
    return answer;
}

int main() {
    vector<int> test;
    test.push_back(3);
    test.push_back(0);
    test.push_back(6);
    test.push_back(1);
    test.push_back(5);

    cout << solution(test) << "\n";

    return 0;
}