알고리즘(C++) / 프로그래머스 level 2 : H-Index

level 2 : H-Index

https://programmers.co.kr/learn/courses/30/lessons/42747?language=cpp 

코딩테스트 연습 - H-Index

 

코드

//프로그래머스 H-Index
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.begin(), citations.end()); //정렬 0 1 3 5 6
    for (int h = 1; h <= citations.size(); h++) {
        int h_less = upper_bound(citations.begin(), citations.end(), h - 1) - citations.begin(); //h번 미만으로 인용된 수 
        int h_more = citations.size() - h_less; //h번 이상 인용된 수
        if (h <= h_more) {
            answer = h;
        }
        else
            break;
    }
    return answer;
}

int main() {
    vector<int> citations = { 3,0,6,1,5 };
    cout << solution(citations) << "\n";
    return 0;
}

 

설명

• citations 벡터를 오름차순으로 정렬한다.
• h의 최댓값을 반복문을 통해서 구한다.
• h_less는 h번 미만으로 인용된 논문 수, h_more은 h번 이상 인용된 논문 수이다. 이를 upper_bound를 통해서 구할 수 있다.
• h_more가 h편 이상을 만족하는 h의 최댓값을 구한다. 

 

고찰

걸린시간 : 25분

생각 외로 너무 금방 풀려서 당황했다. 아직 문제가 명확하지 않아서 일단 풀어봤는데 정답이었다. 이렇게 풀리면 안되는데 풀려버렸다....?

upper_bound와 lower_bound를 알고 있어서 더 쉽게 풀렸다.

2021.08.29 - [알고리즘] - 알고리즘(C++) / 이진 탐색(이분 탐색) - binary_search(), lower_bound(), upper_bound()