<프로그래머스 C++> H-Index 풀이 ( 정렬 )

문제

논문 n편 중 h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용되었을 때 h의 최댓값이 H-Index이다.

이 H-Index를 구하는 문제이다.

---

풀이 아이디어

내림차순 정렬

H-Index의 조건은 "h번 이상 인용된 논문이 h편 이상" 이다.

이 조건을 효율적으로 체크하기 위해선 인용 횟수가 많은 순서대로 논문을 나열하고 현재 인덱스와 인용 횟수를 비교하면 된다.

 

내림차순 정렬 후 i+1번째까지 봤을 때 citations[ i ] >= i + 1이면, "i+1편의 논문이 모두 i+1회 인용됐다" 라는 의미가 된다.

[3, 0, 6, 1, 5] → 내림차순 정렬 → [6, 5, 3, 1, 0]

i=0: citations[0]=6 >= 1    (1편 이상이 1회 이상 인용)
i=1: citations[1]=5 >= 2    (2편 이상이 2회 이상 인용)
i=2: citations[2]=3 >= 3    (3편 이상이 3회 이상 인용)
i=3: citations[3]=1 >= 4  x  → 멈춤

조건이 깨지는 순간, 이전까지의 개수가 H-Index이다.

---

문제풀이

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

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

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

---

코드 흐름

1. 내림차순 정렬

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

인용 횟수가 많은 논문부터 순서대로 나열한다.

greater<int>()를 이용해서 내림차순 정렬한다.

 

2. 조건 체크

if(citations[i] >= i+1)
    answer++;
else
    break;

i + 1은 현재까지 확인한 논문 수이다.

citations[ i ] >= i + 1이면 i + 1편의 논문이 모두 i + 1회 이상 인용됐다는 의미이므로 answer를 증가시킨다.

조건이 깨지는 상황부터는 확인할 필요가 없으니 바로 break한다.

---

핵심 포인트

 

• 내림차순 정렬하면 citations[i] >= i+1 조건 하나로 H-Index를 구할 수 있다.
• 조건이 깨지는 순간 break해서 불필요한 탐색을 줄인다.