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

H-Index

문제 링크

H-Index

분석

h 지수(H-Index)는 모든 논문 중 n회 이상 인용된 논문이 n개 이상일 때, 이 둘을 동시에 만족하는 n의 최대값입니다.
즉, 이 문제는 n의 최대값을 구하는 문제입니다.

오름차순으로 정렬한다면, 특정 인덱스 이후에 나오는 값들을 인덱스 값보다 같거나 큽니다.
내림차순으로 정렬한다면, 특정 인덱스 보다 나오는 값이 작은 경우 인용된 횟수가 n보다 작다는 의미이므로 h 지수가 아니게 됩니다.

입출력 예시로 자세하게 살펴보면 다음과 같습니다.
내림차순으로 정렬한 후 표와 같습니다.

논문 개수	인용 횟수	H-Index
1	6	1
2	5	2
3	3	3
4	1	3
5	0	3

논문 개수와 인용 횟수가 같거나, 논문 개수보다 인용 횟수가 작아진다면 더이상 연산할 필요가 없어집니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    
    // 내림차순으로 정렬
    sort(citations.rbegin(), citations.rend());
    
    // citations를 순회
    for (int i = 0; i < citations.size(); ++i) 
    {
        // 현재 논문의 인용 횟수를 가져와 i개보다 많은지 확인
        if (citations[i] > i)
        {
            ++answer;
        }
        else
        {
            break;
        }
    }
    
    return answer;
}

입출력 예시로 반복문의 실행 순서를 표로 정리하면 다음과 같습니다.

i	논문 개수(i + 1)	인용 횟수(citations[i])	조건 식	H-Index
0	1	6	6 > 0	1
1	2	5	5 > 1	2
2	3	3	3 > 2	3
3	4	1	1 > 3 (종료)	3
4	5	0	0 > 4 (종료)	3

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 정렬 $O(n \ log \ n)$
• citations를 순회하는 반복문 $O(n)$
• $O(n \ log \ n + n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.02ms, 4.2MB)
테스트 2 〉 통과 (0.04ms, 4.21MB)
테스트 3 〉 통과 (0.03ms, 3.69MB)
테스트 4 〉 통과 (0.03ms, 4.13MB)
테스트 5 〉 통과 (0.03ms, 3.67MB)
테스트 6 〉 통과 (0.04ms, 4.16MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.01ms, 4.02MB)
테스트 10 〉 통과 (0.02ms, 4.18MB)
테스트 11 〉 통과 (0.05ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 4.14MB)
테스트 13 〉 통과 (0.04ms, 3.7MB)
테스트 14 〉 통과 (0.03ms, 4.16MB)
테스트 15 〉 통과 (0.04ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.2MB)