[프로그래머스] H-Index

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

 

 

 

문제 및 예시 : 

 

 

 

해결 : 

이진탐색을 활용하여 해결할 수 있는 문제이다.

논문의 수의 범위인 1 ~ citations.size() 사이의 수들의 H-Index 가능 여부를 체크하여, 그 중 가장 큰 값을 정답으로 리턴하면 된다. 

가장 먼저 할 일은 오름차순으로 정렬하는 일이다.  H-Index 가능 여부를 체크하는 수보다 큰 수 중 가장 작은 값을 찾는 과정을 통해 H-Index 가능 여부를 체크하는 수보다 인용횟수가 적은 논문들의 개수를 구한다. 반대로 H-Index 가능 여부를 체크하는 수보다 작은 수  중 가장 큰 값을 찾는 과정을 통해 H-Index 가능 여부를 체크하는 수보다 인용횟수가 많은 논문들의 개수를 구한다.

 

개수를 구하는 과정에서 이진 탐색을 활용한다. 이진 탐색으로 원소를 탐색하는 lower_bound(), upper_bound() 함수를 사용하였다.

lower_bound(A.begin(), A.end(), key)는 오름차순 정렬된 A 배열에서 key와 작거나 작은 수 중 가장 작은 수의 인덱스를 반환한다. 

upper_bound(B.begin(), B.end(), key)는 오름차순 정렬된 B 배열에서 key보다 큰 수 중 가장 작은 수의 인덱스를 반환한다.

 

H-Index 가능 여부를 체크하는 수보다 인용횟수가 적은 논문과  H-Index 가능 여부를 체크하는 수보다 인용횟수가 많은 논문의 갯수를 

H-Index의 조건에 넣어 가능 여부를 확인하고, 가능하다면 그 값들 중 최댓값을 구하여 출력한다. 

 

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

using namespace std;

int answer = 0;
vector<int> cs;

int solution(vector<int> citations) {
    cs = citations;
    sort(cs.begin(), cs.end());
    
    for(int i = 1; i <= cs.size(); i++)
    {
        int upb = upper_bound(cs.begin(), cs.end(), i) - cs.begin();  
        int lb = lower_bound(cs.begin(), cs.end(), i) - cs.begin();
        int notcnt = upb; // 인용된 횟수가 i 이하인 갯수
        int hcnt = cs.size() - lb; // 인용된 횟수가 i 이상인 갯수
        if(cs[lb] == i) hcnt++; // 만약 lower_bound로 찾은 인덱스 값이 i면 인용된 횟수가 i이상인 갯수에 1을 더한다.
        if(notcnt <= i && hcnt >= i) answer = max(answer, i); 
    }
    return answer;
}

 

 

 

참고 : 

lower_bound와 upper_bound에 대한 글

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기