[프로그래머스 코딩테스트 고득점 Kit - 정렬] H-Index

정렬 문제

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

 

유명한 정렬 문제입니다.

https://www.acmicpc.net/problem/12109

물론 백준에도 있습니다.

 

---

[문제 설명]

 

H-Index를 구하는 문제입니다.

 

문제 자체는 어렵지 않은데 H-Index라는 개념을 이해하는 것이 어렵게 느껴질 겁니다.

특히나 프로그래머스의 H-Index설명이 더 구체적이라 헷갈리는 분들도 많을 겁니다.

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

 

지문에서는 위처럼 설명되어 있으나, 사실 밑줄 친 부분만 읽어도 무방합니다.

오히려 밑줄 친 부분만 읽는 것이 이해에 더 도움이 될 수도 있습니다.

 

"나머지 논문이 h번 이하 인용"이라는 부분에 의문이 들 수도 있지만, 밑줄 친 부분을 만족하면 자연스럽게 "나머지 논문이 h번 이하 인용"도 따라서 만족됩니다.

 

 

그렇다면 H-Index를 어떻게 구할 수 있을지 생각해봅시다.

 

어떠한 수 h가 정해졌다면, 인용 횟수가 h 이상인 집합의 크기가 h를 만족해야 합니다.

즉 인용 횟수가 나와있는 citations에서 어떠한 수들의 집합을 따로 뺀 후에, 집합의 최솟값이 집합의 크기보다 크거나 같아야 합니다.

 

그렇다면 이제 남은 문제는 '집합을 어떤식으로 구성하느냐'입니다.

 

한 번에 집합을 딱 알아내고 답을 도출하기에는 무리가 있습니다.

집합의 크기를 늘려가면서 집합의 크기와 집합 내의 최솟값을 비교합시다.

 

그 과정을 효율적으로 수행하기 위해서 정렬을 사용합니다.

내림차순으로 정렬한 후에 0번째 인덱스부터 1씩 증가시키며 (현재 인덱스 + 1)과 현재 인덱스가 가리키는 값을 비교하면 됩니다.

 

왜 이렇게 하면 답이 도출될까요?

 

우선 인덱스입니다.

인덱스가 0부터 시작하여 k번째까지 왔다면 그때까지 지나오면서 본 숫자의 개수는 (k + 1)개 입니다.

즉 (현재 인덱스 + 1)이 가리키는 것은 집합의 크기입니다.

그리고 현재 인덱스가 가리키는 값을 생각해봅시다.

우리는 citations를 내림차순으로 정렬하였습니다.

그 상태에서 인덱스를 0부터 k까지 확인한다면 당연히 citations[k]는 0번째 수부터 k번째 수까지의 최솟값을 가리키게 됩니다.

 

그러므로 위와 같은 방법으로 집합의 크기가 h일 때 최솟값이 h이상인지 알아볼 수 있고, 이는 곧 H-Index이므로 문제를 해결할 수 있습니다.

정렬의 시간 복잡도가 $O(nlogn)$, H-Index를 확인하는 과정이 $O(n)$이므로 총 시간 복잡도는 $O(nlogn)$입니다.

 

---

[소스 코드] / C++

 

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

using namespace std;

int solution(vector<int> ct) {
    sort(ct.begin(), ct.end(), greater<int>());
    
    if (ct[0] == 0) return 0;
    
    int cur = 1;
    while (1) {
        if (cur <= ct.size() && ct[cur - 1] >= cur) {
            ++cur;
        } else {
            --cur;
            break;
        }
    }
    
    return cur;
}