프로그래머스 - H-Index

 코딩테스트 고득점 Kit 정렬 Level 2 문제 H-Index 풀이이다. 이 문제는 정렬 파트에 있지만 사실 논문 수가 최대 1000개, 인용 수가 최대 10000번 이므로 완전 탐색으로 풀어도 10000 * 1000 = 10000000 이므로 1초를 넘지 않는다. 따라서 굳이 sort를 하지 않아도 되는 문제이다.

 

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    int citaSize = citations.size();
    
    sort(citations.begin(), citations.end());
    
    for (int h = 0; h <= 10000; h++)
    {
        int orMore = 0;
        for (auto c : citations)
        {
            if (c >= h)
            {
                orMore++;
            }
        }
        if (orMore >= h && citaSize - orMore <= h)
        {
            answer = h;
        }
    }
    
    return answer;
}