99클럽 코테 스터디 12일차 TIL + 정렬

오늘의 문제 - 정렬

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

---

내 풀이 및 접근 방식

첫 풀이에서 11번 16번 테스트케이스가 실패하여 반례를 찾다가 시간 내에 풀지 못했지만 어쨌든 성공,,...

이분 탐색을 이용하여 풀이했고, 시간 복잡도는 O(n log m) (n은 논문 인용 횟수 배열의 길이, m은 배열의 최대 값)

def solution(citations):
    answer = 0

    start = 0
    end = max(citations)
    
    while start <= end:
        mid = (start + end)//2
        
        # 인용 횟수가 mid 이상인 논문 수 구하기
        cnt = 0
        for n in citations:
            if n >= mid:
                cnt += 1
                
        if cnt >= mid:			# 인용 횟수가 mid 이상인 논문이 mid 이상인 경우
            start = mid + 1		# mid 보다 큰 범위를 조사한다.
            answer = mid		# 최댓값일 수 있으니, answer에 저장
        else:				# 인용 횟수가 mid 이상인 논문이 mid보다 작은 경우
            end = mid - 1		# mid 아래 범위를 조사한다.

    return answer

 

풀이 방식

0부터 가장 큰 논문별 인용 횟수 값까지 이분 탐색을 하여, 논문 인용 횟수가 mid 이상인 논문이 mid 이상을 충족할 때의 가장 큰 mid 값을 찾는 것이 핵심이다. 최댓값을 구하기 위해서 cnt >= mid인 경우에 answer에 mid를 저장해놓는다.

 

처음 풀이에서는 start 값을 min(citations)로 설정해놓는 실수와, answer 값에 cnt를 저장해놓는 실수를 하여 실패했다. min(citations)보다 작은 숫자가 결과값이 될 수 있기 때문에 start값을 0으로 설정해야하고, answer에 cnt를 저장해놓은 것은 그냥 바보같은 실수.. 이것도 모르고 코드 변경만 여러번,,

---

다른 풀이

정렬+max 이용 풀이

def solution(citations):
    citations.sort(reverse=True)
    h = 0
    
    for h_count, i in enumerate(citations, start=1):
        h = max(h, min(h_count, i))
        
    return h
    
# 출처 https://1ets-just-do-it.tistory.com/145

 

풀이 방식

h 값: h 인용 횟수 이상의 논문 개수가 h 이상을 충족하는 h

1. 먼저 인용 횟수가 큰 순서대로 논문을 정렬한다.
2. for문에서 h_count는 논문 인용 횟수이고, i는 h_count 이상인 논문 개수이다.
   "h_count 이상 인용된 논문의 개수는 min(h_count, i) 이상이다" 조건을 충족하기 때문에 h = min(h_count, i)이다.
   각 요소를 순회하며 이전의 h 값이랑 비교하며 가장 최대인 h 값을 구한다.

"h_count 이상 인용된 논문의 개수는 min(h_count, i) 이상이다"  를 충족하는 이유를 아래 예시로 이해해보자

 

ex1) 논문 인용 횟수 리스트: 9, 6, 4, 4, 4, 3, 3, 2, 1

• 9 인용 횟수(h_count) 이상의 논문 개수는 1(인덱스+1)이다. => h: 1
• 6 인용 횟수 이상의 논문 개수는 2이다. => h: 2
• 4 인용 횟수 이상의 논문 개수는 5이다. * 3번 반복시 => h: 4

ex2) 논문 인용 횟수 리스트: 9, 6, 4, 3, 1

• 9 인용 횟수(h_count) 이상의 논문 개수는 1(인덱스+1)이다. => h: 1
• 6 인용 횟수 이상의 논문 개수는 2이다. => h: 2
• 4 인용 횟수 이상의 논문 개수는 3이다. => h: 3

h_count와 본인과 앞 요소의 개수를 합한 개수 중 최솟값이 항상 h가 되는 것을 확인할 수 있다.

 

시간 복잡도

• citations.sort(reverse=True): Python의 내장 정렬 함수는 Timsort 알고리즘을 사용하며, 평균 및 최악의 경우 시간 복잡도는 O(n log n)입니다.
• for h_count, i in enumerate(citations, start=1): 배열의 모든 요소를 순회하므로 이 루프의 시간 복잡도는 O(n)입니다.
• 루프 내의 연산: h = max(h, min(h_count, i))는 상수 시간 연산(O(1))입니다. 따라서 루프 내부의 연산은 전체 시간 복잡도에 큰 영향을 미치지 않습니다.

전체적으로 O(nlogn) 시간 복잡도를 가진다.

 

m의 범위가 더 크기도 하고, 이분 탐색을 쓴 풀이보다 아래 for문 코드가 더 효율적이고 직관적인 것 같다.

---

회고

오랜만에 이분탐색 코드 복기해서 좋았다.

최댓값 구하기 최솟값 구하기 때 분기처리를 어떻게 하면 좋을지 기억해두면 좋을 것 같다.

 

enumerate의 경우 종종 for문에서 인덱스랑 값을 같이 쓰기 위해서 사용했었는데, start 매개변수 쓰는 것은 처음 봤다.

enumerate(sequence, start)

enumerate의 경우, sequence와 start를 매개변수로 갖는다. 반복가능한 객체 sequence를 입력받고, start를 이용하여 시작하는 인덱스를 설정해준다. 예를 들어, [5, 3, 4, 2] 와 같은 sequence를 입력받고 start=1로 설정했을 때, 반환값은 [(1,5), (2, 3), (4,3), (2,4)]이다. start부터 1씩 증가시킨 인덱스값과, 반복객체의 요소값을 튜플로 반환하는 것이다.