프로그래머스 - H-Index - C++

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

프로그래머스

 

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

int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(),citations.end(),greater<>());
    
    int num=citations[0];
    
    while(num>=0)
    {
        int cnt=0;
        for(int j=0;j<citations.size();j++)
        {
            if(citations[j]>=num)
                cnt++;
        }
        if(cnt>=num)
            return num;
        
        num--;
    }
    
    return answer;
}

 

h-index 는 어떤 과학자가 낸 n편의 논문 중 h번 이상 인용된 논문이 h편 이상인 조건에 맞는 h의 최댓값이다. 

 

따라서 내림차순 정렬로 가장 큰 수를 기준으로 h를 시작한다.

(h==num)

num을 기준으로 num보다 크면 num값보다 많이 인용됐으니 카운트한다.

 

for문을 다 돌았을 때, num보다 많이 카운드됐다면 h-index이다. 따라서 가장 큰 값부터 1씩 내리며 확인했기 때문에 최댓값이다. 

 

하지만 이 방법은 정렬을 한 의미가 없는 코드이다. 

정렬과 관계없이 모든 원소를 계속 순회하기 때문이다. 

 

chatgpt에 물어보니 

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

int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(),citations.end(),greater<>());
    
    for(int i=0;i<citations.size();i++)
    {
        if(citations[i]<i+1)
            return i;
    }
    
    
    return citations.size();
}

다음과 같은 코드를 알려줬는데 한번의 반복문으로 답을 처리한다. 

아직 완벽히 이해되지 않지만 정렬한 데이터를 가지고 적절한 조건문을 넣으면 한번에 처리가 가능하다는 것을 알게 된 것 같다. 

 

이해되지 않는 부분은 citations[i] < i + 1 부분이다. 

citations[i] <= i+1 일 때 i+1 리턴과 citations[i] <=i 일때 i 리턴이 무슨차이가 있길래 전자는 오답 후자는 정답인지 모르겠다.