programmers H-Index C++

programmers : https://programmers.co.kr/learn/courses/30/parts/12198

프로그래머스

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

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

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

programmers 정렬 level2 H-Index 문제입니다.

 

문제를 이해못하셨을 수도 있으니 간단히 설명하면 다음과 같습니다

 

예제에 있는 3 0 6 1 5 의 경우 3, 5, 6은 3이라는 값보다 모두 '이상' 이고 0, 1은 3이라는 값보다 모두 '이하' 입니다

테스트케이스를 하나 더 만들어보겠습니다.

3 5 7 7 7 7 7 7 의 테스트케이스의 경우 답은 무엇일까요? ==> 6이 됩니다.

7 7 7 7 7 7 이 6개의 수는 모두 6이상이고, 3, 5는 6이하 이기 때문이죠

 

접근법은 결국 정렬을 하신 후에, 이분탐색을 이용하는 것입니다.

 

초기 answer답을 0, 탐색 인덱스 idx를 0으로 설정해보겠습니다.

 

처음에 3을 만났네요? size - idx = 8이므로 answer는 당연히 3으로 초기화됩니다.

5를 만났습니다. size - idx = 7 이므로 answer는 5로 초기화 됩니다.

7을 만났습니다. size - idx = 6 이므로 7이라는 값은 정답이 될 수 없겠습니다.

현재 answer : 5, 탐색중인 수 : 7

이 2개의 수로 이분탐색을 해보면

(5+7)/2 = 6일때 size - idx = 6 을 만족하게 되네요!

그래서 정답이 6이 되는 것이고, 6보다 큰 H-Index를 찾을 수 없을테니 탐색을 종료해주시면 되는겁니다.

 

코드는 다음과 같습니다~

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> citations) {
    int answer = 0;

    sort(citations.begin(), citations.end());

    // h번 이상 인용된 논문이 h개이고
    // 나머지 논문들은 h개 이하로 인용되었다

    // 3 5 7 9 10 -> answer : 4
    // 3 5 7 7 7 7 7 7 -> answer : 6 
    for (int i = 0; i < citations.size(); i++) {
        int temp = citations[i];
        if (citations.size() - i >= temp) answer = max(answer, temp);
        else {
            // temp보다는 작지만 answer 보다는 커질수 있음을 의미함
            // 이분탐색으로 answer와 temp 사이의 적합한 수를 찾음
            int s = answer;
            int e = temp;
            int m;
            while (s < e) {
                m = (s + e) / 2;
                if (citations.size() - i > m) s = m + 1;
                else if (citations.size() - i == m) {
                    s = m;
                    break;
                }
                else e = m;
            }
            answer = max(answer, s);
            break;
        }
    }

    return answer;
}