[C++/13333] Q-인덱스

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

lower_bound를 사용해서 문제를 해결하는데, 범위가 0부터 1000까지 이기 때문에 충분히 해결할 수 있습니다. lower_bound는 시간복잡도 logN이기 때문에 확실히 처리할 수 있습니다. 

한 학생이 발표한 총 n ≥ 1 편의 논문 중에서, k번 이상 인용된 논문이 k편 이상이고 나머지 n − k 편의 논문들 인용회수가 각각 k 번 이하라면, 해당 학생의 q-인덱스는 k이다.

문제는 이러합니다. k번 이상 인용된 논문이 k편 이상, 나머지 n - k 편의 논문들의 인용회수가 k번 이하라면? q인덱스는 k 이다. 즉 k번이 처음 시작되는 위치를 찾아내면 되는 문제입니다. 아래는 정답 코드입니다.

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

#define MAX 1010
using namespace std;

int n,number;
vector<int> v;

void init() {
	
	cin >> n;
	
	
	for(int i = 0; i < n; i++){
		cin >> number;
		v.push_back(number);
	}
	
	sort(v.begin(), v.end());
	
}

void solve() {
	
	for(int i = 1000; i >= 0; i--){
		
		vector<int>::iterator iter = lower_bound(v.begin(), v.end(), i);
		if(i <= v.end() - iter){
			cout << i;
			return;
		}
		
	}
	
	
}

int main() {
	
	init();
	solve();
	
	return 0;
}