[LEETCODE 150] - 274 H-Index

LeetCode의 274번 문제인  "H-Index" 문제이다.

이문제는 두가지 방법으로 풀어봤다.

 

문제 핵심 : H-index = h편 이상의 논문이 각각 최소 h번 이상 인용된 최대 h.

 

1. 카운팅(버킷) 풀이

정답 풀이(Python)

class Solution: 
	def hIndex(self, citations: List[int]) -> int:
    n = len(citations) paper_counts = [0] * (n+1)
    for c in citations: paper_counts[min(n, c)] += 1 
    
    h = n 
    papers = paper_counts[n] 
    
    while papers < h: 
    	h -= 1 
        papers += paper_counts[h] 
        
    return h

 

아이디어

h-index는 최대가 n(논문 수)을 넘을수 없고, 인용수가 n보다 커도 h-index 계산에는 "n 이상"으로만 묶어도 충분하다 그래서 min(n, c)로 n 초과 인용은 n 버킷에 몰아넣는다.

 

paper_counts[k] 의미

- 인용 횟수가 정확히 k(단, k=n은 n 이상 포함)인 논문의 수

 

뒤에서부터 누적하는 이유

• papers를 "현재 h 이상 인용된 논문수"로 유지하고싶다, 처음에 h = n 일때, papers = paper_counts[n]는 "n 이상 인용된 논문 수" 만약 papers < h 라면, h를 줄이면서(조건 완화) 해당 인용수에 해당하는 논문들을 누적해 papers를 늘림

while 루프가 뜻하는 것은?

• "h 이상 인용된 논문 수(papers)가 h보다 작으면 아직 h-index가 성립 안 함 -> h를 낮추자"
• 처음으로 papers >= h 가 되는 순간의 h가 최대 h-index

2. 정렬 풀이

citations list를 내림차순으로 정렬한다.

idx의 값이 citation의 값보다 커질경우 return 한다. 그렇지 않을 경우에는 idx + 1 값을 return한다. 

class Solution: 
	def hIndex(self, citations) -> int:
    	if not citations:
        	return 0
        citations.sort(reverse=True)
        for idx, citation in enumerate(citations):
        	if idx + 1 > citation:
            	return idx
        return idx + 1

아이디어

내림차순 정렬하면

• idx 번째 논문은 (0-index이므로) "현재까지 논문 수"가 idx+1 이때 citation이 idx+1 이상이면, "상위 idx+1 개 논문이 모두 최소 idx + 1회 이상 인용" 일 가능성이 유지됨

조건 idx + 1 > citation의 의미

• 상위 idx+1개 논문 중 가장 인용수가 낮은 논문이 citation인데, 그 논문이 idx+1번 미만 인용이면, "idx+1 편이 각각 idx+1번 이상 인용" 조건이 깨짐 따라서 그 직전까지의 최대 값이 idx가 됨.

마지막 return idx +1

• 루프를 끝까지 통과했다는 건
  • 모든 위치에서 idx+1 <= citation을 만족했다는 뜻
• 그러면 h는 n까지 가능하므로 마지막 값 반환