프로그래머스 H-Index 파이썬

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

코딩테스트 연습 - H-Index

 

 

첫번째 풀이 O(N^2)

def solution(citations):
    answer = 0

    citations.sort(reverse=True)
    citation_count = [0] * (citations[0] + 1)
    for i in citations:
        for j in range(0, i):
            citation_count[j] += 1

        citation_count[i] += 1
    print(citation_count)
    for i in range(len(citation_count) - 1, -1, -1):
        if i <= citation_count[i]:
            answer = i
            break
    return answer

 

1. 최대 인용횟수 만큼의 크기를 가진 배열을 생성한다 (citation_count)

2. citations 를 순회하며 각 원소 이하의 숫자를 모두 카운트한다

 

[3, 0, 6, 1, 5] 인 경우,

1,2 의 과정을 마치면 [5, 4, 3, 3, 2, 2, 1] 이 된다.

 

해석해보면 차례로 해석해보면 아래와 같다.

 

인용횟수가 0 이상인 논문 5 회

인용횟수가 1 이상인 논문 4 회

인용횟수가 2 이상인 논문 3 회

인용횟수가 3 이상인 논문 3 회

인용횟수가 4 이상인 논문 2 회

인용횟수가 5 이상인 논문 2 회

인용횟수가 6 이상인 논문 1 회

 

H-index 는 H번 이상 인용된 논문이 H편이상이여야 하므로 역순으로 순회하면서 정답을 구하는 과정을 해석하면 아래와 같다

 

인용횟수가 6 이상인 논문 1 회      탈락: H번 이상 인용된 논문이 H편이상이 아니다

인용횟수가 5 이상인 논문 2 회      탈락: H번 이상 인용된 논문이 H편이상이 아니다

인용횟수가 4 이상인 논문 2 회      탈락: H번 이상 인용된 논문이 H편이상이 아니다

인용횟수가 3 이상인 논문 3 회      합격: H번 이상 인용된 논문이 H편이상이다: 정답은 인용횟수인 3이다. 코드상으로는 인덱스 i 다. 배열을 역순으로 순회했기 때문에 합격을 만나자마자 그 값이 최대값이다. 그러므로 break

인용횟수가 2 이상인 논문 3 회      여기부터는 볼 필요가 없다. 왜냐하면 이미 H 의 최대값은 나올 수가 없기 때문이다.

인용횟수가 1 이상인 논문 4 회      여기부터는 볼 필요가 없다. 왜냐하면 이미 H 의 최대값은 나올 수가 없기 때문이다.

인용횟수가 0 이상인 논문 5 회      여기부터는 볼 필요가 없다. 왜냐하면 이미 H 의 최대값은 나올 수가 없기 때문이다.

 

 

여기까지가 내가 생각하고 풀었던 방식이다. 별로 어렵지 않게 풀었다.

하지만... 다른사람 풀이를 보고 그 풀이를 해석하느라 많은 시간을 고민했다..

 

다른사람의 풀이 O(N)

def solution(citations):
    citations = sorted(citations)
    l = len(citations)

    for i in range(len(citations)):
        if citations[i] >= l - i:
            return l - i
    return 0

 

이게 어떻게 되는걸까... 정말 많은 고민을 했다.

 

고민하면서 깨달은점은 아래와 같다.

 H-Index 는 H번 이상 인용된 논문이 H편 이상이여야 하므로 절대 전체 논문수보다 커질 수 없다.

즉, n 보다 커질 수가 없다.

 

풀이 과정은 아래와 같다.

 

1. 배열을 오름차순으로 정렬한다.

 

2. 배열을 순회하며 남은 문서수 보다 인용횟수가 크거나 같은지 비교 한다. if citaions[i] >= l - i:

이부분이 이해가 어려웠다..

 

배열이 [10,20,30,40,50] 와 같이 정렬되어있다고 할 때

 

이 배열은 정렬되어있으므로 배열이 정렬되어있으므로 첫번째 요소인 10 이후의 값은 모두 10보다는 크거나 같다.

 

그러므로 배열의 첫번째 요소인 10번 이상 인용된 논문이 5편 이상 이다. 라고 생각할 수 있다.

 

그리고 H-index 의 조건은 H번 이상 인용된 논문이 H편 이상 이니 H가 5라면 결국 아래와 같이 해석된다.

 

5번 이상 인용된 논문이 5편 이상 이여야 한다.

 

이를 조건으로 쓰면

 

if citations[0] >= l-p:

즉 10이 남은 문서수보다 크거나 같으면 H-index 에 부합하다는 것이다.

 

첫번째 요소인 10번은 5번 이상이므로 5번 이상 인용된 논문이 5편 이상 이여야 한다 는 조건에 부합한다.

 

조건을 충족하는 순간, 그 값이 최대값이다.

그 이후 값들은 문서의 수가 줄어들면서 더이상 최대 H-index 가 나올 수 없다.