[C++][Programmers][정렬] H-Index

[문제]

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

프로그래머스

 

[해결법]

[3, 0, 6, 1, 5] 가 있을 때 h번 이상 인용된 논문 횟수가 h개 이상이고 나머지가 h번 이하로 인용되면 된다.

즉, h = 1일 때 -> 1번 이상 인용된 논문이 1개 이상이어야 함. 나머지가 1이하로 인용되어야 함.

      h = 2일 때 -> 2번 이상 인용된 논문이 2개 이상이어야 함. 나머지가 2이하로 인용되어야 함.

      h = 3 일 때 -> 3번 이상 인용된 논문이 3개 이상이어야 함. 나머지가 3이하로 인용되어야 함.

          .

          .

          .

(오답)

h 값을 1부터 1씩 늘려가며 배열을 다 돌면서 판단할 것인가... 그러기엔 제한사항의 숫자 값이 너무 큼(무조건 시간초과)

벡터를 오름차순 정렬한 후 h 값을 0부터 1씩 늘려가며 탐색하다가 h값 이상인 수를 만나면 "벡터 길이 - h" 값으로 큰 값의 개수를 찾아준다. 그리고 그 값이 h개이면 정답으로 리턴한다.

-> 문제를 덜 이해한거다... [4, 3, 3, 3, 3] 케이스의 정답이 3인데 위 처럼 짜면 3번 이상 인용된 논문이 5개라서 3을 도출안한다.

-> h 값을 0부터 1씩 늘려서 찾을 필요 없이 내림차순 정렬한 벡터를 순환하면서 인용된 횟수 < h index를 만족하는 h index를 찾으면 된다.

 

4 3 3 3 3

첫번째 논문 4의 h index는 1

두번째 논문 3의 h index는 2

세번째 논문 3의 h index는 3

네번째 논문 3의 h index는 4인데 h index보다 인용된 논문 횟수가 작으므로 탐색을 멈추고 3을 리턴한다.

 

 

엣지 케이스 참고...

 

[알아둘 것]

벡터 내림차순 정렬

sort(v.begin(), v.end(), greater<int>());

 

[코드]

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

int solution(vector<int> citations) {
    int answer = 0;
    
    //answer값 구하기 쉽게 내림차순 정렬. 6 5 3 1 0
    sort(citations.begin(), citations.end(), greater<int>()); 
    
    // 최대값이 0이면 0 출력
    if(!citations[0]) { return 0; }
    
    //citations 벡터 돌면서 h번 이상 인용되었는지 체크
    for(int h = 0; h < citations.size(); h++){           
        if(citations[h] > h) answer++;
        else break;
    }
    
    return answer;
}