1. 공부한 내용

문제1 - 99 클럽 - h-index 2:

[ 문제 풀이 ]

문제는 h-index를 구하는 문제로, h-index란 주어진 리스트가 오름차순으로 정렬되었을 때, i번 째 요소가 i이상을 만족하는 최대의 i를 구하는 것이다. (이 때 설명의 i는 1부터 시작) logarithmic time을 만족하도록 문제에서 명시했으므로 나는 Binary Search로 접근하였다.

나의 풀이는 다음과 같다.

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if citations[mid] == n - mid:
                return n - mid
            elif citations[mid] < n - mid:
                left = mid + 1
            else:
                right = mid - 1
        return n - left

Binary search 코드를 위와 같이 짜고, 각 턴의 citations[mid] 값이 n-mid와 일치하는지 확인한다. 그리고 이보다 작으면 좌측 값을 mid+1로, 크면 우측 값을 mid - 1로 조정한다.

⇒ 다른 사람의 숏코딩을 참고하면 배열을 내림차순으로 변경 후, for문으로 처음부터 값을 조회했으나 이렇게 할 경우 시간 복잡도가 높아지기 때문에 비 효율적이다.

2. 오늘의 회고

오늘은 기본적인 Binary search 문제였다. 나는 반복문 형식을 채택하여 문제를 풀이하였으나, 다음에는 재귀함수를 활용해서 풀이해보자.

아자자 화이팅.