H-Index

문제

---

문제의 시간복잡도

n의 개수가 1000개이다. 그래서 $O(n^2)$안에 풀면은 된다라고 생각을 했다.

---

풀이

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

using namespace std;

bool compare(pair<int,int> a, pair<int,int> b)
{
    return a.first > b.first;
}

int solution(vector<int> citations) {
    int answer = 0;
    unordered_map<int,int> map;
    for(int i=0;i<1001;i++)
    {
        if(i < citations.size())
        {
            if(map.end()==map.find(citations[i]))
            {
                map.insert(make_pair(citations[i],1));
            }
            else
            {
                map[citations[i]]++;
            }
        }
        
        
        if(map.end()==map.find(i) && i!=0)
        {
            map.insert(make_pair(i,0));
        }
    }
    
    vector<pair<int,int>> v(map.begin(),map.end());
    sort(v.begin(),v.end(),compare);
    
    for(int i=0;i<v.size();i++)
    {
        if(v[i].first <= v[i].second)
        {
            int flag = 1;
            for(int j=i+1;j<v.size();j++)
            {
                if(v[j].second > v[i].first)
                {
                    flag = 0;
                    v[i+1].second += v[i].second;
                    break;
                }
            }
            if(flag == 1)
            {
                answer = v[i].first;
                break;
            }
        }
        else
        {
            v[i+1].second += v[i].second;
        }
    }
    return answer;
}

//생산성과 영향력을 나타내는 지표 = H-Index
//H-Index = h
//논문 n편중에서 H-index번 이상 이용된 논문이 H-index편 이상이고 나머지 논문이
//H-index번 이하 인용됐다면 H-index의 최댓값이 이 과학자의 H-Index이다.


//논문중에서 인용이 h번 이상된 논문이 h편 이상이다. ex) 2번 인용된 논문이 2편이상이면 H-index가 2인것이다.
//이러한 H-index값이 최대인 경우가 h이다.

//논문의 수는 1000개, n^2까지는 괜찮을듯?
//인용횟수가 0번~1만번, 예를 들어서 하나의 논문에 1만번 인용이 되었는데 근데 그 논문에만 인용이 됐다면 
//H-index =1인것
//인용수가 많으면 좋다. 하지만 이 인용수와 같은 값이 h개만큼 있어야한다.
//map을써서 숫자를 센다. 그리고 map을 vector로 변환하여 sort한다. 큰 수 부터 그리고 두 수가 같거나 더 많은 경우를 찾는다. 그리고 만약에 안됐다. 그러면 현재 값을 뒤에 더해준다.

//나머지 논문이 h번 이하 인용됐는지도 확인해야하는가 ? 
//나머지 논문이 h번 이하라는 것은 무슨 소리인가? 나머지를 다 확인을 해봐야 한다.

//독해력이 문제인가, 질문하기 부분에서 힌트를 얻고 다시 진행을 했다.
//[6, 5, 5, 5, 3, 2, 1, 0], 4 인 테스트케이스에서 문제가 발생을 한다.
//바로 h-index가 꼭 citations 안에 들어간 값이 아닌 경우가 있기 때문이다.

---

접근법

해시테이블을 하나 생성하여 citations의 각 원소가 몇번씩 들어가는지를 카운팅 하였다.
만약에 원소에 없는 요소라면 인용횟수를 0으로 초기화하고 해시테이블에 저장한다.
이를 key값(인용된 횟수)을 기준 내림차순으로 정렬을 한다.
이렇게 정렬한 배열의 요소들을 하나하나씩 확인한다.
인용한 횟수 <= 인용한 논문의 수 가 만족을 하면 for문을 통해서 뒤쪽 원소들 중에서
(뒤)인용한 논문 수 > 인용한 횟수(앞) 를 만족하는 원소가 있다면,

flag = 0;
v[i+1].second += v[i].second;
break;

위의 코드를 실행해준다. 지금 보고있는 논문의 인용횟수를 다음 원소의 인용횟수에 더해주는 것이다. 왜냐하면 인용한 논문의 수 이상의 값을 확인하고 있기 때문이다.

---

피드백

생각해보니 굳이 1000번씩이나 for문을 돌 필요가 없었다. citations에 들어간 가장 최댓값 만큼만 돌면서 해결을 해도 됐다.

---

걸린시간 & 힌트사용유무

43분 15초.

질문하기에서 힌트 테스트케이스 하나를 받음.