[정렬] h-index - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

처음에 생각했던 포인트는

 

어떠한 조건을 만족하는 것 중에서 가장 큰 값을 찾는 문제이고

이를 가장 빠르게 처리할 수 있는 방법론은 바로 binary search라고 생각을 했습니다

 

문제 예시의 3 0 6 1 5의 예시를 보면

우선 첫 번째로 정렬을 우선 해 준 다음 → 0 1 3 5 6 (nlogn)

저 중에서 Lower bound와 Upper bound를 적절히 조절하여 h값이 가장 크게 하는 값을 찾는 논리입니다.

이러한 접근법으로 문제 풀이를 시도하였습니다.

 

방법론을 자세하게 보면 다음과 같습니다

Lower Bound = 0

Upper Bound = max(citations)

다음과 같이 설정해준 다음에 중간 값을 기준으로 h값이 될 수 있는 지를 체크합니다.

이 경우

이 경우 처음 후보가 되는 3을 check하지만 3은 h_index가 될 수 업습니다

 

따라서 bound를 조정하여 search를 해줍니다.

0 6

다음 후보군의 2의 경우 가능합니다

따라서 2는 h_index가 될 수 있는 후보가 됩니다

 

하지만 2가 무조건 최적의 정답이 될 수 없기에 계속해서 search를 해줍니다.

4의 경우도 h_index가 될 수 없기에 동일하기 upper를 줄여줍니다

 

반복문 탈출 뒤에 같아지는 시점의 3보다 하나 더 큰 4까지 확인을 해준 과정을 거친 다음 조건을 종료합니다

 

여기서 두 가지 중요한 binary search의 조건이 들어갑니다.

 

1) 왜 반드시 Lower Bound가 0부터 시작하는가

최소 값을 기반으로 하면 안되는가?

 

2) 왜 반복문 탈출 뒤에 한번 더 체크해주는 과정을 거치는가

 

1)의 경우 다음 예제를 참고해봅시다

 

6, 7, 8, 9

다음의 경우를 생각해보면

Lower = 6, Upper = 9이라고 하면

binary search로 찾는 모든 후보군이 다 h_index를 만족할 수 없음

하지만 h_index는 꼭 반드시 저 배열의 요소가 될 필요가 없습니다

이 문제의 경우 h_index의 답은 4입니다

 

2)의 경우 다음 예제를 참고해봅시다

 

1 8 9 10 11 12

 

다음 예제의 경우 binary_search로 쭉 찾아

반복문을 탈출할 때에는 Lower = 4, Upper=4로 답이 나옵니다.

하지만 이 문제의 경우 4보다 5의 경우가 h_index의 답임을 알 수 있습니다

Boundary check에서 "//2"의 연산으로(내림처리) 인해 늘 작은 값이 뽑히므로

이보다 1 더 큰 경우를 마지막에 체크해주는 과정이 필요합니다

 

또한 추가적으로 중요한 부분이

한 편의 논문도 인용이 되지 않은 [0, 0, 0, 0]의 경우

사실상 연산을 할 필요가 없으므로 바로 0을 return해주었습니다

따라서 이러한 모든 조건들을 고려해서

코드를 짠 결과는 다음과 같습니다

# h번 이상 인용된 논문 count
def check(h, citations) :
    count = 0
    for n in citations :
        if n >= h :
            count += 1
    return count

def solution(citations) :
    answer = 0
    ## binary search를 위한 정렬
    citations = sorted(citations)
    ## Lower bound, Upper bound 설정 
    L = 0; U = len(citations);
    ## 후보군
    represent = 0
    c1 = 0

    ## 모든 논문이 0편 인용될 시, 예외처리
    if max(citations) == 0 : return 0
    
    ## binary search
    while(L < U) :
        h = (L+U)//2
        c1 = check(h, citations)
        if h <= c1 :
            represent = h
            if answer < represent : answer = represent
            L = h+1
        else :
            U = h-1

    ## 후보가 될 수 있는 모든 후보들 check
    for rep in [L-1, L, L+1] : 
				## 여기서 answer를 갱신할 수 있으면 갱신
        if rep <= check(rep, citations) : 
            if answer < rep : answer = rep
    return answer

 

시간 복잡도

sorted ⇒ nlogn

check 함수 → n * binary search → logn ⇒ nlogn

따라서 총 시간 복잡도는 nlogn이 나옴!!

 

 

이 외에도 다른 binary search로 푼 코드들이 있나 살펴보다 질문하기에 이분 탐색으로 푸신 분이 있길래 내용을 참고해봄

이 분은 훨씬 더 간단하게 문제를 푸심 → 현타 온다... 나중에 공부하자

 

def bsearchF(arr, h) : 
	start = 0
	end = h
		
	while(start < end) : 
		h = (start + end + 1) // 2 ## 올림처리인가?
		if(h <= arr[h-1]) : 
			start = h ## bound 갱신을 이렇게 했네?
		else : 
			end = h-1
	return start ## L 반환한 건 same

def solution(citations) : 
	n_max = len(citations) # upper bound는 논문 수로
	citations.sort(reverse=True) # 이 부분은 아이디어 똑같은듯
	print(citations)
	answer = bsearchF(citations,n_max)

	return answer

Binary Search 에서 중요한 부분 꼭 기억하자

Lower Bound와 Upper Bound 설정

Mid 값 조정 → 내림과 올림

종료 조건 설정 (L<U)