[리트코드] 274. H-Index

문제

https://leetcode.com/problems/h-index/?envType=study-plan-v2&envId=top-interview-150

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Example 2:
Input: citations = [1,3,1]
Output: 1

 

Constraints:

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

---

✔ 문제접근 #1 완전탐색[통과] ⭕

Intuition
전체 배열을 순회하며 h-index가 될 수 있는 최댓값을 찾는다.

Algorithm
1부터 배열의 길이까지 h-index가 될 수 있는지 판단한다. h-index가 될 수 있다면 최댓값을 갱신해준다.

class Solution:
    
    def is_h_index(self, citations, i):
        count = len([x for x in citations if x >= i]) # O(N)
        
        if count >= i:
            return True
        return False
        
    
    def hIndex(self, citations: List[int]) -> int:
        
        # 접근 1. 완전탐색
        n = len(citations)
        ans = 0
        
        for i in range(1, n + 1): # O(N)
            if self.is_h_index(citations, i):
                ans = i
        
        return ans

 

Complexity Analysis

• 시간 복잡도 : O(N*N)
  • 배열크기만큼 반복 O(N)
  • h-index확인하기 위한 배열 탐색  O(N)
  • 그러므로 전체시작복잡도 : O(N * N)

• 공간복잡도 : O(N)
  
  • h-index가 가능한지 확인하기위해 리스트사용

---

✔ 문제접근 #2 카운팅[통과] ⭕

Intuition

카운팅방식을 통하여 특정 값 이상의 값이 몇번나왔는지 기록한다.

Algorithm
nums[i]의 최댓값은 1000이기때문에 1000크기의 count배열을 생성한다.

count배열의 index i값이 citations배열에 몇번 나오는지를 기록한 다음, h-index를 만족하는 최대 i 값을 구해준다.

완전탐색이 배열 크기인 5000 * 5000 이었다면, 카운팅하는 방식은 5000 * 1000이기때문에 조금더 최적화를 할 수 있다.

def hIndex(self, citations: List[int]) -> int:

    # 접근 2. 카운팅 정렬
    MAX_VAL = 1001
    count = [0] * MAX_VAL
    max_c = max(citations)

    for i in range(0, max_c + 1):
        c = 0
        for x in citations:
            if i <= x:
                c += 1
        count[i] = c

    ans = 0
    for i in range(max_c + 1):
        if count[i] >= i:
            ans = i
    return ans

 

Complexity Analysis

• 시간 복잡도 : O(M *N)
  • 카운트배열을 채우기 위하여 1000번 순회 O(M)
  • citations 순회 O(N)
  • 그러므로 전체시작복잡도 : O(M * N)

• 공간복잡도 : O(M)
  
  • 크기 최대 1000(M)만큼의 count 배열 사용

---

기타풀이 및 회고

주어진 배열의 크기가 최대 5000으로 크지 않았기 때문에 완전탐색을 이용해서 O(N*N)으로 풀 수 있을 것이라고 생각하였다.

완전탐색 말고 조금더 최적화를 시킬 수 있을까를 고민해 봤을 때, citations[i]값의 최댓값이 1000인점을 고려해서 카운팅정렬을 생각할 수 있었다. 5000*5000 에서 5000*1000로 시간복잡도를 줄일 수 있었다.

크기를 잘 고려한다면 카운팅 방식도 충분히 활용가능 할 것 같다.