[ 내 풀이 ]
#include <string> #include <vector> #include <numeric> #include <algorithm> using namespace std; int solution(vector<int> citations) { int answer = 0; int sum=0; vector<int> cnt(10002,0); for(int i=0;i<citations.size();i++) { cnt[citations[i]]++; } sort(citations.begin(), citations.end()); for(int i=citations.size()-1;i>=0;i--){ sum = accumulate(cnt.begin()+(i+1), cnt.end(), 0); if(sum >= i+1){ answer = i+1; break; } } return answer; }
- 직관적으로 생각할 수 있는 풀이 (시간복잡도가 좋지는 않아보임)
1) 계차수열을 이용해서 n번 이용된 논문의 개수를 모두 구한다
2) n번 이상 인용된 논문의 개수가 n보다 크거나 같으면 break!
[ 최적 코드 ]
#include <string> #include <vector> #include <numeric> #include <algorithm> using namespace std; int solution(vector<int> citations) { int answer = 0; // 내림차순으로 정렬 sort(citations.begin(), citations.end(), greater<int>()); for(int i=0;i<citations.size();i++) { if(citations[i] >= i+1){ answer++; }else{ break; } } return answer; }
- h-index를 1씩 증가하는 것이 포인트
- 내림차순하여 확인한 값이 현재 인덱스+1인 (i+1) 보다 크거나 같다면
--> 적어도 (i+1)번 이상 인용된 논문이 있다는 뜻!ex)
[5,3,2,1,0] 일 때 !
( i+1 = 1 / value = 5 ) : h-index증가
( i+1 = 2 / value = 3 ) : h-index증가
( i+1 = 3 / value = 2 ) : break!
즉 , h-index는 2 ! (2번 이상 인용된 논문이 2개 이상이라는 의미)