99클럽 코테 스터디 26일차 TIL - 배열, 이진탐색 (LeetCode 275번)

항해99 코테 스터디 26일차 문제인 리트코드의 275번은 주어진 인용수 배열을 통해 H-index를 구하는 문제다. 난이도는 Medium이며 완전탐색 또는 이진탐색을 통해 해결할 수 있다.

 

오늘의 문제 - 275. H-Index II 문제 정보

문제 키워드

- 배열, BS

난이도

- Medium

 

문제 요약

• 정수 배열 citations가 주어지는데, citations[i]는 논문 i의 인용수를 나타낸다.
  • citations는 오름차순으로 정렬되어 있다.
  • 1 ≤ citations.length ≤ 100,000
• H-Index를 반환하라.
  • H-Index: 최소 h개의 논문이 h번 이상 인용되었을 때 h의 최대값
  • ex) [0,1,3,5,6] → h-index=3 (3번이상 인용된 논문이 3개 이상임)

 

문제 풀이 과정  

•  

• 오름차순으로 정렬되어 있으므로, 앞에서부터 순회하면서 h값을 구해 최댓값을 갱신한다.
• i번째의 인용값(h)과 i부터 마지막까지의 개수(cnt)를 비교한다. (인용수 h이상인 논문이 총 cnt개)
  • 인용값보다 개수가 많거나 같으면 인용값으로 정답을 갱신한다.
  • 인용값보다 개수가 적으면 개수로 정답을 갱신한다.
• 위 과정을 진행해보면, 결국 인용수보다 남은 개수가 적어지는 시점이 정답이 되므로, 이진탐색을 통해 더 빠르게 찾을 수 있다. → O(logN) 코드

 

코드

class Solution {

		// O(n)
    public int hIndex(int[] citations) {
        int n = citations.length;
        int answer = 0;

        for(int idx=0; idx<n; idx++) {
            // h 이상이 cnt개
            int h = citations[idx];
            int cnt = n - idx;

            if (h <= cnt) {
                answer = Integer.max(answer, h);
            } else {
                // 남은 개수보다 h값이 크면 더이상 h-index가 커질 수 없음
                answer = Integer.max(answer, cnt);
                break;
            }
        }

        return answer;
    }

		// O(logn)
    public int hIndex_2(int[] citations) {
        int n = citations.length;
        int l = 0, r = n-1;

        while(l <= r) {
            int mid = (l+r)/2;

            // 인용수보다 남은 개수가 적으면 오른쪽 탐색, 많거나 같으면 왼쪽 탐색
            if (citations[mid] < n - mid) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }

        // 마지막으로 확인한 시작 인덱스(l) ~ 마지막 논문(n-1)까지의 개수가 h-index가 됨
        return n - l;
    }
}

• 시간복잡도: 첫번째 방법 O(n), 두번째 방법 O(logn)
• 공간복잡도: O(1)

 

오늘의 학습 회고

새롭게 알게된 것

• 정렬된 배열을 탐색하는 풀이에서 종료조건이 명확하다면, 이진탐색을 사용할 수 있는지 생각해보자.