[프로그래머스] Python3 - H Index

프로그래머스의 레벨 2 문제 H Index

문제 요구 조건

조건에 맞는 h의 최댓값을 구해야한다.

내 풀이 방법

1. 첫 번째 방법. 범위가 작으므로 완전탐색을 하면 n^2 으로 풀 수 있다.
2. 두 번째 방법. 역순으로 정렬하고, 순회할 때 하나씩 세면서 citation이 h보다 클 때 h를 1씩 증가시키면 h는 h보다 높은 citation의 수가 된다. 따라서 h의 최댓값을 구할 수 있다.

# h의 최댓값을 구해야함
# h 값의 범위는 0~1000
# 배열을 정렬하고 0부터 1000까지 조회하면서 가장 큰 h를 찾자
# 6 6 5 5 3 1 0 -> 4
def solution(citations):
    answer = 0
    citations.sort(reverse=True)
    for i, citation in enumerate(citations): # n^2
        for h in range(1001):
            if citation >= h and i+1 >= h:
                answer = max(answer, h)
    return answer

def solution2(citations):
    citations.sort(reverse=True)
    h = 0
    for citation in citations: # n
        if citation > h:
            h += 1
    return h

print(solution([3, 0, 6, 1, 5]))