[Programmers] 42747번 - H-Index [Java][C++]

문제 링크

---

1. 문제 풀이

H-Index는 h번 이상 인용된 논문이 h편 이상일 때 h의 최댓값이다. 이 문제는 정렬을 활용하면 간단하게 해결할 수 있는데 먼저 주어진 citations를 오름차순으로 정렬한다. [3, 0, 6, 1, 5]의 경우 [0, 1, 3, 5, 6]이 된다. 이렇게 정렬을 하면 특정 논문보다 인용 횟수가 많은 논문은 전부 오른쪽에 위치하게 되고 인용 횟수가 동일한 논문들에 대해 인덱스가 가장 앞서는 논문은 해당 논문보다 인용 횟수가 많거나 같은 논문들도 전부 오른쪽에 위치하게 된다.

이후 첫 번째 원소부터 마지막 원소까지 H-Index의 후보들을 탐색해나가면 된다.

• 첫 번째 원소는 0이며 0보다 인용 횟수가 많거나 같은 논문은 5편이 있다. 따라서 0은 H-Index 후보가 된다.
• 두 번째 원소는 1이며 1보다 인용 횟수가 많거나 같은 논문은 4편이 있다. 따라서 1은 H-Index 후보가 된다.
• 세 번째 원소는 3이며 3보다 인용 횟수가 많거나 같은 논문은 3편이 있다. 따라서 3은 H-Index 후보가 된다.
• 네 번째 원소는 5이며 5보다 인용 횟수가 많거나 같은 논문은 2편이 있다. 따라서 5는 H-Index 후보가 못되지만 5보다 작은 수인 2 이상인 논문이 2편 이상인 것은 확실하므로 여기서 2는 H-Index 후보가 된다.
• 다섯 번째 원소는 6이며 6보다 인용 횟수가 많거나 같은 논문은 1편이 있다. 따라서 6은 H-Index 후보가 못되지만 6보다 작은 수인 1 이상인 논문이 1편 이상인 것은 확실하므로 여기서 1은 H-Index 후보가 된다.

모든 후보 중 가장 큰 수인 3이 최종 H-Index가 된다. 항상 주어진 논문의 인용 횟수 중에서 정답이 존재하는 것이 아님에 주의해야 한다. 예를 들면 citations가 [3, 3]일 경우 H-Index는 2가 된다.

아니면 Lower Bound 이분 탐색을 활용하면 좀 더 직관적으로 해결할 수 있다. H-Index는 0 이상 citations의 원소 중 최댓값 이하이므로 citations를 정렬 후 citations의 최댓값부터 0까지 반복문을 돌며 반복 변수 i 이상인 논문의 수 cnt가 i 이상이라면 바로 i를 반환해도 된다.(i를 반환하는데 i가 작아지는 방향으로 반복이 진행되므로 처음 찾는 순간이 최댓값이다.)

---

2. 코드

1. 정렬 [Java]

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);

        int max = 0;
        for (int i = 0; i < citations.length; i++) {
            max = Math.max(max, Math.min(citations[i], citations.length - i));
        }

        return max;
    }
}

2. 이분 탐색 [Java]

문제 조건에서 논문이 1편 이상 존재하며 i는 0까지 순회하므로 -1을 반환할 일을 없다.

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);

        for (int i = citations[citations.length - 1]; i >= 0; i--) {
            int cnt = citations.length - lowerBound(citations, i);
            if (cnt >= i) return i;
        }

        return -1;
    }

    static int lowerBound(int[] arr, int key) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = (left + right) / 2;

            if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

3. 정렬 [C++]

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

using namespace std;

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

    int mx = 0;
    for (int i = 0; i < citations.size(); i++) {
        mx = max(mx, min(citations[i], (int)citations.size() - i));
    }

    return mx;
}

4. 이분 탐색 [C++]

문제 조건에서 논문이 1편 이상 존재하며 i는 0까지 순회하므로 -1을 반환할 일을 없다.

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

using namespace std;

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

    for (int i = citations.back(); i >= 0; i--) {
        int cnt = citations.end() - lower_bound(citations.begin(), citations.end(), i);
        if (cnt >= i) return i;
    }

    return -1;
}

---