[Programmers][Python] H-index

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

 

처음 작성한 코드

h 번 이상 인용된 논문이 h 편 이상인 조건을 잘 이용을 해보자.

반대로 말하면 인용된 논문이 많은 논문부터 h 편을 나열하면 h 번째 논문은 h 번 이상 인용돼야 한다.

• 입력된 배열 citiations을 오름차순으로 정렬한다.
  
  • 루프문에서 pop 함수를 이용해 역순으로 값을 가져올 것이다.
• 루프문에서 h를 1부터 행렬의 최대 길이까지 반복한다.
  • h를 0부터 하지 않은 이유는 0번 이상 인용된 논문이 0편 이상인 경우는 당연히 존재한다.
  • 때문에 max_h 변수를 0으로 초기화 하였고, 루프문에서는 1부터 진행한다.
  • 인용된 논문이 많은 논문부터 h 편을 나열하면 h 번째 논문은 h 번 이상 인용되야 한다.
    • 아래와 같은 프로세스로 진행 된다. 
      • 1 번째 논문은 1 번 이상 인용되었는지 확인한다.
      • 2 번째 논문은 2 번 이상 인용되었는지 확인한다.
      • ...
      • h 번째 논문은 h 번 이상 인용되었는지 확인한다.
    • 만약 h 번째 논문이 h 번 이상 인용되었다면 max_h 변수를 h로 설정해준다.
    • 만약 h 번째 논문이 h 번 이상 인용되지 않았다면 h 번째 이후의 논문은 h 번 이상 인용될 수 없으므로 뒤에 사례를 확인할 필요없이 루프문을 탈출해주면된다.

def solution(citations):
    citations.sort()
    max_h = 0

    for h in range(1, len(citations) + 1):
        if citations.pop() >= h:
            max_h = h
        else:
            break
    return max_h
    
# 입출력 예시
print(solution([3, 0, 6, 1, 5]))

처음에는 포인터를 이용하거나 h 번 이상 인용된 논문이 h 편 이상인 조건 그대로 사용하려 해서 코드가 복잡해졌었다.

pop을 이용한 이유는 값을 순차적으로 확인하기 때문에 루프문에서 시간복잡도가 최대한 적게 만들고 싶었다.

 

다른 코드

[코드1]

처음 작성한 코드와 비슷하게 행렬 citations을 인용된 논문이 많은 순서대로 배열해 h와 비교하는 알고리즘이다.

• 한 줄 안에 함수가 여러 개 들어있어 이해하기 힘들 수 있지만 입출력 예시 [3, 0, 6, 1, 5]를 이용하여 확인해 보자.
• 먼저 내림차순으로 행렬 citations를 정렬해 준다.
• list(enumerate(citations, start=1))
  • 1부터 시작되는 행렬과 정렬된 ciations를 쌍으로 묶는다.
  • [(1, 6), (2, 5), (3, 3), (4, 1), (5, 0)]
• list(map(min, enumerate(citations, start=1)))
  • 쌍들의 목록에서 최솟값만 출력하여 매핑한다.
  • [1, 2, 3, 1, 0]
• max(map(min, enumerate(citations, start=1)))
  • 최댓값을 찾는다.
  • 3

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

• 불필요한 작업이 들어있지만, 결과적으로는 두 쌍으로 묶고 최솟값을 구할 때 아래 두 조건을 고려하게 된다.
  • h 번 이상 인용된 논문이 h 편 이상인 조건
  • h 번째 논문은 h 번 이상 인용

 

[코드2]

이분탐색을 이용한 풀이

import bisect

def solution(citations):
    citations.sort()
    for i in range(max(citations),-1, -1):
        tmp = bisect.bisect_left(citations, i)
        if i <= len(citations) - tmp:
            return i