[프로그래머스] H-Index

문제 설명 및 주의점

문제를 간략히 설명하자면 위키피디아의 H-index의 정의를 인용하면서 그걸 구해보라고 하는 내용이다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다.

예를 들어, 논문들의 인용 횟수 배열이 [ 3, 0, 6, 1, 5 ] 로 주어졌다면
3번 이상 인용된 논문이 3편 이상이고 나머지 논문은 3번 이하로 인용되었으므로 H-Index는 3이다.

하지만 문제엔 숨겨진 조건이 있었는데, 가능한 H-Index 중 가장 큰 값을 찾으라는 것이다.
(질문 게시판 안 봤으면 절대 몰랐을 뻔 했다)

예를 들어 다시 위의 예시에서, 1번 이상 인용된 논문이 1편 이상(4편) 이고 나머지 논문은 1번 이하로 인용되었으므로 1도 조건에 해당하지만, 정답은 최대 값인 3이다.

 

아이디어

우선, 인용값 배열을 정렬 하고, 정렬한 배열에 적용 가능한 탐색 함수를 정의하기로 했다.
그 탐색 함수로, 특정 값이 들어가는 적절한 위치를 찾아주는 함수 lowerBound를 만들어서 사용하기로 했다.

lowerBound함수로 특정 값이 들어가는 적절한 위치 중 가장 앞을 찾아주면 아래와 같이 사용할 수 있다.

[3, 0, 6, 1, 5] → 정렬 → [ 0, 1, 3, 5, 6 ]

0을 삽입하기에 적절한 위치 : 0 → 0 이상 인용된 논문의 개수 : 5-0 = 5
1을 삽입하기에 적절한 위치 : 1 → 1 이상 인용된 논문의 개수 : 5-1 = 4
2를 삽입하기에 적절한 위치 : 2 → 2 이상 인용된 논문의 개수 : 5-2 = 3
3을 삽입하기에 적절한 위치 : 2 → 3 이상 인용된 논문의 개수 : 5-2 = 3
4를 삽입하기에 적절한 위치 : 3 → 4 이상 인용된 논문의 개수 : 5-3 = 2
...

표로 나타내면 아래와 같다

찾는 값 (i)	삽입하기에 적절한 위치 (idx)	찾는 값 이상 인용된 논문 개수 (n-idx)
0	0	5
1	1	4
2	2	3
3	2	3
4	3	2
5	3	2
6	4	1
7	5	0

 

이렇게 모든 경우의 수를 다 찾을 수 있고, 어떤 값이 H-Index가 가능한지 판별할 수 있다

찾는 값 이상으로 인용된 논문 개수 >= 찾는 값

가능한 값들 중 가장 큰 것을 return해주면 된다.

 

구현

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

using namespace std;

int lowerBound(vector<int>& a, int num) {
    int n = a.size(), i;
    for(i = 0 ; i < n ; i++) {
        if(a[i] >= num) 
            break;
    }
    return i;
}
int solution(vector<int> a) {
    int answer = 0;
    int n = a.size();
    
    sort(a.begin(), a.end());

    int idx = 0;
    for(int i = 0 ; idx < n && i <= 10000 ; i++) {
        idx = lowerBound(a, i);

        if(n-idx >= i) 
            answer = i;
    }
    return answer;
}