[리트코드][JAVA] 275. h-index-ii (H-지수 II)

💡 문제
h-index-ii (https://leetcode.com/problems/h-index-ii/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

1. 배열 (Array)

배열은 동일한 데이터 타입의 요소들이 연속적으로 저장된 자료구조입니다. 각 요소는 인덱스를 통해 접근할 수 있습니다. 배열의 주요 특성은 다음과 같습니다:

• 고정된 크기: 배열은 선언 시 크기가 정해지며, 후에 크기를 변경할 수 없습니다.
• 인덱스: 각 요소는 인덱스를 가지며, 인덱스는 0부터 시작합니다.
• 연속적인 메모리 배치: 배열의 요소들은 메모리에 연속적으로 저장됩니다.
• 빠른 접근: 인덱스를 사용하여 O(1) 시간복잡도로 요소에 접근할 수 있습니다.

2. 정렬된 배열 (Sorted Array)

정렬된 배열은 요소들이 오름차순 또는 내림차순으로 정렬되어 있는 배열입니다. 정렬된 배열의 주요 특성은 다음과 같습니다:

• 이진 탐색 가능: 요소가 정렬되어 있기 때문에 이진 탐색을 사용하여 특정 값을 빠르게 찾을 수 있습니다.
• 삽입 및 삭제의 어려움: 정렬된 상태를 유지하기 위해 요소를 추가하거나 삭제할 때 추가적인 작업이 필요합니다.
• 탐색 속도: 일반적으로 선형 탐색보다 빠르게 요소를 찾을 수 있습니다.

3. 이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 특정 값을 찾는 데 사용되는 효율적인 탐색 알고리즘입니다. 이진 탐색의 특성은 다음과 같습니다:

• 중간 요소 기준 탐색: 배열의 중간 요소와 목표 값 비교를 통해 탐색 범위를 반으로 줄입니다.
• 시간 복잡도: O(log n)으로, 배열의 크기에 비례하여 비교 횟수가 증가하지 않습니다.
• 전제 조건: 정렬된 배열에서만 사용할 수 있습니다.

---

🤓 문제 풀이

🔨 문제 설명

연구자가 각 논문에서 받은 인용 수를 나타내는 정수 배열 citations가 주어졌을 때, citations[i]는 해당 연구자가 i번째 논문에서 받은 인용 수이며, citations는 오름차순으로 정렬되어 있습니다. 연구자의 h-지수를 반환하세요.

위키백과의 h-지수 정의에 따르면: h-지수는 주어진 연구자가 최소한 h번 인용된 논문을 h편 이상 발표한 최대값으로 정의됩니다.

로그 시간에 실행되는 알고리즘을 작성해야 합니다.

예제 1:

입력: citations = [0,1,3,5,6] 출력: 3 설명: [0,1,3,5,6]은 연구자가 총 5편의 논문을 발표했으며, 각각 0, 1, 3, 5, 6번 인용되었음을 의미합니다. 연구자는 3편의 논문이 각각 최소한 3번 인용되었고, 나머지 두 편은 3번 이하로 인용되었기 때문에, h-지수는 3입니다. 예제 2:

입력: citations = [1,2,100] 출력: 2

제약 조건:

n == citations.length 1 <= n <= 105 0 <= citations[i] <= 1000 citations는 오름차순으로 정렬되어 있습니다.

 

이 문제는 오름차순으로 정렬된 논문 인용 수 배열을 가지고 연구자의 h-지수를 찾는 문제입니다. h-지수는 주어진 연구자가 최소한 h번 인용된 논문을 h편 이상 발표한 최대값을 의미합니다. 문제를 해결하기 위해 효율적인 O(log n) 시간 복잡도를 갖는 알고리즘을 작성해야 합니다.

요약

• 주어진 배열 citations는 오름차순으로 정렬되어 있으며, 연구자가 발표한 논문마다 받은 인용 수를 나타냅니다.
• 목표는 연구자의 h-지수를 찾는 것입니다. h-지수는 최소 h번 인용된 논문이 h편 이상인 경우의 최대 h 값을 의미합니다.

---

🔨 접근 방법

• 이진 탐색 사용: 오름차순으로 정렬된 배열에서 특정 조건을 만족하는 값을 찾는 데에 이진 탐색이 적합합니다.
• 조건 설정: 배열의 중간값을 선택하여 해당 논문이 h-지수를 만족하는지 확인합니다. 이 때, h는 현재 논문의 인덱스와 전체 논문 수를 사용하여 계산합니다.
• 탐색 범위 조정: 중간값이 h-지수 조건을 만족하면 오른쪽 범위를 줄이고, 그렇지 않으면 왼쪽 범위를 줄입니다.
• 반복: 이진 탐색을 반복하여 최종적으로 h-지수를 찾습니다.

---

🔨 문제 풀이 과정

• 초기화 : left는 0, right는 배열의 길이 n으로 설정합니다.
• 중간값 계산: mid는 (left + right) / 2로 계산합니다.
• 조건 확인: citations[mid]가 n - mid (남은 논문의 수) 보다 크거나 같은 경우, 왼쪽 범위를 조정하고 그렇지 않으면 오른쪽 범위를 조정합니다.
• 최종적으로 left가 right를 넘어서면 h-지수를 반환합니다.

---

🔨 이진 탐색을 사용하는 이유

배열이 이미 오름차순으로 정렬되어 있기 때문에 이진 탐색을 적용하면 효율적으로 문제를 해결할 수 있습니다.이진 탐색은 정렬된 배열에서 특정 조건을 만족하는 값을 찾는 데 매우 유용하며, 시간 복잡도는 O(log n)입니다.

 

---

🔨 구현코드

class Solution {
    public int hIndex(int[] citations) {
        // n은 논문의 개수
        int n = citations.length;
        
        // 탐색 범위를 설정
        int left = 0, right = n;
        
        // 이진 탐색 시작
        while (left < right) {
            // 중간 인덱스를 계산
            int mid = (left + right) / 2;
            
            // 중간 값이 h-지수 조건을 만족하는지 확인
            // n - mid는 현재 인덱스부터 끝까지의 논문 개수
            if (citations[mid] >= n - mid) {
                // 조건을 만족하면 오른쪽 범위를 줄인다
                right = mid;
            } else {
                // 조건을 만족하지 않으면 왼쪽 범위를 늘린다
                left = mid + 1;
            }
        }
        
        // 최종적으로 h-지수를 반환
        return n - left;
    }
}

---

📚 풀이 보완

코드 설명

• 변수 초기화: left를 0으로, right를 배열 길이 n으로 초기화합니다.
• 이진 탐색 루프: left가 right보다 작은 동안 반복합니다.
  • mid 값을 계산하여 현재 중간값을 찾습니다.
  • citations[mid]가 n - mid보다 크거나 같으면 right를 mid로 설정하여 탐색 범위를 줄입니다.
  • 그렇지 않으면 left를 mid + 1로 설정하여 탐색 범위를 늘립니다.
• 결과 반환: 최종적으로 left 값에 의해 결정된 h-지수를 반환합니다.

이 방법은 O(log n)의 시간 복잡도로 문제를 해결할 수 있습니다.

---

📍 Plus+

시간 복잡도

1. 이진 탐색의 기본 원리:
   • 배열의 중간 요소를 선택하고, 목표 값을 찾기 위해 배열을 절반으로 나누는 과정을 반복합니다.
   • 각 단계에서 탐색 범위가 절반으로 줄어들기 때문에, 최대 로그(base 2) n 번의 비교가 필요합니다.
2. 연산 횟수:
   • 배열의 길이를 절반으로 줄이는 연산은 O(log n) 단계에서 완료됩니다.
   • 비교 연산과 인덱스 계산은 상수 시간 (O(1))이 소요됩니다.

따라서, 전체 시간 복잡도는 O(log n)입니다.

공간 복잡도

1. 추가 메모리 사용 없음:
   • 알고리즘은 입력 배열 citations 외에는 별도의 추가적인 공간을 사용하지 않습니다.
   • 단지 몇 개의 변수 (left, right, mid 등)만 필요합니다.
2. 고정된 메모리 사용:
   • 이 변수들은 입력 크기 n에 의존하지 않으므로, 공간 복잡도는 입력 크기와 무관하게 상수입니다.

따라서, 전체 공간 복잡도는 O(1)입니다.

요약

• 시간 복잡도: O(log n)
• 공간 복잡도: O(1)

 

---

풀이 참고 로직