[알고리즘] 프로그래머스 H-Index 파이썬

SCY·2023년 9월 8일

✅ 문제

✅ 나의 풀이

(통과하지 못한 코드들 입니다)

첫번째

def solution(citations):
    answer = 0
    citations.sort()
    h = citations[-1]
    while answer == 0 :
        cnt1 = 0
        cnt2 = 0    
        for c in citations:
            if c >= h:
                cnt1 += 1
            if c <= h:
                cnt2 += 1
        if (cnt1 >= h) and (cnt2 <= h):
            answer = h
            break
        h -= 1
    return answer

h를 가장 큰 값부터 하나씩 감소시키며 조건을 충족하는 즉시 answer로 반환하는 알고리즘이다. 이 경우 최대라는 조건도 함께 만족된다. 그러나, [0, 1, 2, 10000]과 같이 불필요한 계산이 많아지는 경우 시간 초과가 분명히 발생하는 코드일 것이다. 결국 위 코드는 하나의 케이스에서 시간 초과되어 통과되지 못했다.

두번째

def solution(citations):
    answer = 0
    citations.sort()
    start = citations[0]
    end = citations[len(citations)-1]
    while start <= end:
        h = (start + end) // 2
        cnt = 0
        for c in citations:
            if c >= h:
                cnt += 1
        if cnt >= h and (len(citations) - cnt) <= h:
            start = h + 1
            answer = h
        else:
            end = h - 1
    return answer

하나씩 탐색하는 것은 무리가 있어 이진 탐색으로 작전을 변경했다.
그러나 또 하나의 케이스에서 실패했다.

    if answer == 0 :
        answer = len(citations)

위 예외 처리도 추가해보았으나, 이번에도 또 다른 하나의 케이스에서 실패했다.

검색을 통해 나의 문제를 발견했다.
H-Index의 개념을 완벽히 이해하지 못한 것이다.

H-Index란, h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용되었을 때 h의 최댓값이다.

이 때 "나머지 논문이 h번 이하 인용"을 "나머지 논문의 수가 h편 이하"로 착각한 상태로 구현했다. 옳게 해석하면, "나머지 논문"은 결국 h번 미만 인용된 논문이므로 항상 h번 이하 인용되었다는 조건을 만족하게 된다.

정리하자면 h는 "인용 횟수가 h번 이상인 논문의 수가 h편 이상"을 만족하는 최댓값이다.

✅ 다른 풀이

def solution(citations):
    citations.sort(reverse=True)
    for i, c in enumerate(citations):
        if i >= c:
            return i
    return len(citations)