프로그래머스 정렬 H-Index c++ 풀이

문제 설명

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

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

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

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citationsreturn

[3, 0, 6, 1, 5]

3

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

※ 공지 - 2019년 2월 28일 테스트 케이스가 추가되었습니다.

 

문제 풀이

 

보자마자 단순하게 엥 내림차순으로 정렬하고 i=0 부터 하나씩 짚으면서 볼 때 논문 인용 횟수 == i+1 일 때 아니야?

하고 코드 써서 실행해봤는데 바로 테스트케이스 통과해버림ㅋ 

 

본인의 천재성에 감탄하며 제출했으나

 

^^ 

 

다시 해보자

일단 조건은 두개이다.

1. h번 이상 인용된 논문의 갯수가 h개 이상이어야 한다.

2. 나머지 논문은 h번 이하로 인용되어야 한다.

1번이 충족되면 2번은 당연히 충족되므로 2번은 고려할 필요가 없다.

노트에 끼적여 가면서 내가 놓친게 뭘까? 생각해봤다.

나는 인덱스를 기준으로 무조건 h는 배열에 주어진 피인용 수 중 하나일 것이다 라고 자연스레 생각하고 있었는데, 아니다.

예를 들어 다음과 같은 케이스에서,

피인용 수	논문 갯수
10	1
7	2
4	3
2	4
0	5
0	6

내 기존 코드로 하면 답은 2가 나온다.

실제 H-index는 3이다.

꼭 피인용 수가 H-index가 되지는 않는다.

 

코드를 다시 짜봤다. 피인용수만 도는게 아니라. 최대 피인용 수 부터 0까지 모든 수를 조사해야 한다.

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations)
{
    sort(citations.begin(), citations.end(), greater<int>());

    for (int i = 0; i < citations.size(); ++i)
        for (int h = citations[i]; h > citations[i + 1]; --h)
            if (i + 1 >= h)
                return h;
    return 0;
}

설렁설렁 짜고 범위 에러나 그런거 나지 않을까 생각하면서 넣었는데 웬열ㅋ 올패스함ㅋ

 

예외처리 할 필요없는 완벽 로직^^

실무에서도 이러면 좋겠다...

 

다른 사람의 코드

 

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

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());

    for (int i = 0; i < citations.size(); ++i) {
        if (citations[i] < i + 1) {
            return i;
        }
    }

    return citations.size();
}

?? 내 초기 코드와 저 비교 부호(?) 만 빼고 완전 똑같다.

생각해보니 h의 범위는 0~최대 피인용수가 아니라 0~논문의 개수 이다.

나처럼 전자로 계산을 해버리면 피인용 수 범위가 클 때 시간이 매우 오래 걸릴 것이다...

근데 이거 댓글로 틀렸다는 의견이 있던데 귀찮아서 더 생각해보지는 않을 것이다.