[99클럽 코테 스터디 18일차 TIL] 배열

📖 오늘의 학습 키워드
배열

오늘의 회고

문제

[H-Index II]
https://leetcode.com/problems/h-index-ii/description/

나의 해결

class Solution {
    public int hIndex(int[] citations) {
        int hIdx = 0;
        int left = 0;
        int right = citations.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(citations[mid] >= citations.length - mid) {
                hIdx = citations.length - mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }        
        return hIdx;
    }
}

for문을 돌며 h-index를 구해도 문제가 풀리지만, 문제에서 알고리즘의 시간 복잡도가 로그 시간을 가져야 한다고 했기 때문에 이진 탐색을 이용해 문제를 풀었다.

1. left는 배열 인덱스의 최솟값인 0으로 초기화하고,
   right는 배열 인덱스의 최댓값인 citations.length - 1로 초기화한다.
2. 이진 탐색을 진행해 h-index를 구한다.
   1) left와 right의 중간인 mid 값을 구한다.
   2) citations[mid] 값이 citations 배열의 길이에서 mid를 뺀 값보다 크거나 같으면, 이를 h-index 값으로 저장하고 right 값을 mid에서 1을 뺀 값으로 갱신한다.
   3) 반대로 작으면 left 값을 mid에서 1 더한 값으로 갱신한다.