[LC150] H-Index (Binary Search & Greedy)

H-Index 문제 

 

 

이 문제 역시 예전에 풀려고 하다가 못 풀었던 문제인데 이전과 똑같이 그리디한 방법으로 풀려고 했다. 먼저 citations 배열을 정렬한 다음에 citations[i], 현재 citation된 갯수가 n-i 한 갯수보다 작을 때 max 값을 없데이트 하는 방식으로 풀었다. 

 

 

 

이렇게 코드를 작성할 경우, citations = [3, 0, 6, 1, 5] 일 경우에는 잘 동작한다. 

 

i가 3일때는 if 조건문이 false가 되서 더 이상 h 값이 업데이트 되지 않고 for 문이 종료가 되고 h 값은 3이 된다. 이때는 정답인데, input 값이 citations = [100] 일 경우 문제가 된다. 

 

i가 일때 n - i >= citations[i] 조건을 만족하지 못하기 때문에 h가 업데이트 되지않고 default 값이 0이 되고 이건 오답이다. h 값이 업데이트 됐어도 오답인데, n이 1개이고 첫번째 논문이 인용된 수가 100이면 H 인덱스는 최대 1이 되는 게 맞다. 그래서 이 로직을 수정하려고 열심히 노력해봤으나... 점점 내 코드는 미궁속으로.....

 

결국 gpt랑 다른 사람들의 solutions을 참고해서 답을 작성했는데 보통 i를 뒤에서부터 찾는데 나는 0부터 시작하는 코드로 작성했기 때문에 0 -> n 순서에 맞게 코드를 작성해봤다. 수정된 코드는 다음과 같다. 

 

 

배열이 정렬되어 있으면 인덱스 i 보다 작은 인덱스의 값은 i 보다 작다. 그리고 인덱스 i 보다 큰 인덱스의 값은 i 보다 크다. h는 최대 n개 (논문의 갯수) 이기 때문에 초기 값을 n으로 세팅한다음 하나씩 줄여가면서 답을 찾는다. h가 citations[i] 보다 클 경우, citations[i]는 h-index를 무조건 만족한다. 따라서, citations[i] 보다 큰 값들 중에 정답이 있는지 계속 찾고 h <= citations[i] 보다 작거나 같으면 더이상 h-index를 만족하는 큰 값이 없기 때문에 바로 리턴한다. 제대로 설명이 됬는지 모르겠는데, 나는 이 로직을 이해하는게 너무 힘들었다. 

 

 

 

 

하지만 이 문제를 푸는데 다른 방법이 또 있었다는 사실! 그리디 보다 코드는 더 길지만 훨씬 직관적인 바로 binary search를 사용한 풀이인데 binary search는 정렬되어 있고 답이 어느 범위 안(within a certain range)에 있으면 사용할 수 있다. 

 

 

문제의 constraint를 보면 citations[i] 는 0부터 1000까지인데 h-index의 최대 범위는 최대 인용 수 1000을 넘을 수가 없다. 따라서 h-index는 0부터 1000사이의 값이 되고, 풀이는 다음과 같다. 

 

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int hIndex = 0;

        Arrays.sort(citations); // 정렬 (O(n log n))

        int left = 0, right = 1001; // hIndex의 가능한 범위 [0, 1001]

        while (left <= right) {
            int mid = left + (right - left) / 2; // overflow 방지를 위한 중간값 계산

            // citations 배열에서 mid 이상인 첫 인덱스를 찾음 (lower_bound 역할)
            int lbIdx = lowerBound(citations, mid);
            int citedAtLeastMid = n - lbIdx; // mid 이상 인용된 논문 수

            if (mid <= n && citedAtLeastMid >= mid) {
                hIndex = mid;     // 현재 mid는 가능한 h-index
                left = mid + 1;   // 더 큰 h-index가 있는지 오른쪽 탐색
            } else {
                right = mid - 1;  // 유효하지 않으므로 왼쪽 탐색
            }
        }

        return hIndex;
    }

    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;

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

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

        return left; // target 이상의 첫 번째 인덱스
    }
}

 

 

c++ 에 있는 lowerbound/upperbound 함수를 자바에서도 제공해주는 걸로 알고있는데 저 위에 lowerBound 메소드를 직접 구현한 것보다는 

 

이 코드가 더 직관적인 것 같다.