[프로그래머스] H-Index (정렬)

문제 소개

오늘 풀었던 프로그래머스 - H-Index 문제를 정리합니다.

이 문제는 어떤 과학자의 논문 인용 기록을 보고, H-Index를 구하는 문제입니다.
H-Index란, h번 이상 인용된 논문이 h편 이상이고, 나머지 논문은 h번 이하 인용된 경우의 h값 중 최댓값을 의미합니다.

문제 링크: H-Index - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 논문의 인용 수 배열을 오름차순 정렬합니다.
2. 인용 수(a)와  a번 이상 인용한 논문 수(b)를 비교하여, 가능한 h의 최댓값을 찾습니다.
3. 구체적으로, citations[i](=인용수 a)와 (논문 총 개수 - 현재 인덱스)(= a번 이상 인용한 논문 수 b) 중 더 작은 값을 h의 후보로 삼아 최댓값을 갱신합니다.
   
   • a >= b 일 경우 h = b : b번 이상 인용된 논문 b편 이상(a번 이상 인용된 논문이 b개 이므로) / (b번 이하 인용된 나머지 논문이 몇편인지 상관없음 0편도 가능)
   • a <= b 일 경우 h = a : a번 이상 인용된 논문 a편 이상 (a <= b) / 나머지는 a번 이하 인용됨 (오름차순 정렬)

---

해결 과정 및 코드

핵심 아이디어

1. 정렬된 상태에서,
   • 현재 논문의 인용 수 citations[i]와
   • 현재 인용 수 이상 인용한 논문 개수 (citations.length - i)
2. 이 둘 중 작은 값을 h 후보로 보고, 가장 큰 h를 구한다.

코드

시간 복잡도 O(N log N)

• O(N log N) : 정렬
• O(N) : 한 번 순회하며 h값 계산

 

import java.util.*;

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

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

        return max;
    }
}

---

카운팅 배열로 풀 경우

아이디어

1. citations 배열을 순회하면서,
   각 인용 횟수별 논문 개수를 기록한다. (ex: citations=3 이면 3번 인용된 논문이 +1)
2. 그리고 높은 인용 수부터 논문을 모아가며,
   "h번 이상 인용된 논문이 h편 이상" 되는 지점을 찾는다.
3. 시간 복잡도 : O(n)

class Solution {
    public int solution(int[] citations) {
        int n = citations.length;
        int[] count = new int[n + 1]; // n 이상은 모두 count[n]에 저장

        for (int c : citations) {
            if (c >= n) count[n]++;
            else count[c]++;
        }

        int total = 0;
        for (int i = n; i >= 0; i--) {
            total += count[i];
            if (total >= i) {
                return i;
            }
        }
        return 0;
    }
}

(예시: citations = [3, 0, 6, 1, 5])

• count 배열 만들기:
  • 0회: 1개
  • 1회: 1개
  • 3회: 1개
  • 5회: 1개
  • 6회: 1개 (6 ≥ 5니까 count[5]에 추가)
  ⇒ count = [1, 1, 0, 1, 0, 2]
• 이제 뒤에서부터(total 누적):
  • i=5 → total=2 (5 이상 아님)
  • i=4 → total=2 (4 이상 아님)
  • i=3 → total=3 (3 이상! → 정답은 3)