[알고리즘] 프로그래머스 H-Index - Python

문제 : 프로그래머스 H-Index 문제

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

프로그래머스

 

문제를 봤을 때 가장 먼저 생각난 것은 주어진 citations 배열을 정렬하는 것이었다. 정렬을 먼저 하고, 이후에 for 반복문을 돌면서 h회 이상 인용된 논문의 개수를 세어나가는 것으로 코드를 작성했다. 처음 작성한 코드는 아래와 같다.

 

def solution(citations):
    answer = 0
    citations.sort()
    l=len(citations)
    for i in range(l):
        paper=l-i
        if citations[i]==paper:
            return paper
    return answer

 

하지만 이 코드에서 간과했던 문제는 citations[i]==paper일때만 paper를 리턴하는 것이다. 따라서 예외 상황을 생각해보았을 때 citations=[0, 0, 5, 3], result : 2 인 경우가 있다. 이 케이스에서 위의 코드로는 답이 0으로 나오게 된다. 하지만, H-index의 정의를 보면 정확히 h 이상 인용된 논문이 정확히 h편일 필요는 없고, h편 이상이면 되는 것이다. 따라서 아래와 같이 수정을 했다. 

 

def solution(citations):
    answer = 0
    citations.sort()
    l=len(citations)
    for i in range(l):
        paper=l-i
        if citations[i]>=paper:
            return paper
    return answer

 

이렇게 했을 때는 예외상황 없이 모두 테스트 케이스를 통과했다. == 비교를 >=로 변경하면서 H-index의 결과가 항상 citations 배열에 있을 필요는 없는 상황을 반영해준 것이다. 

 

최종 코드의 시간 복잡도를 생각해보았다. 

• citations 배열 정렬하는 과정 : O(n log n)
• for문 반복하는 과정 : O(n)

항상 효율적인 코드를 짜기 위해서는 시간복잡도를 먼저 작성해보고 코드에 반영하는 것이 중요하다는 것을 알게되었다. 이번 글부터는 시간 복잡도를 함께 작성하도록 하겠다.