99클럽 코테 스터디 12/99일차 TIL #H-Index(미들러)

문제:H-Index


출처: 프로그래머스

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

프로그래머스

 

1. 문제 설명

제한사항

2. 문제 해석

논문을 쓴 경험이 있는 사람들은 H-Index가 뭔지 들어봤을 것이다.

나 역시도 H-Index를 알고는 있지만 이걸 어떻게 구현을 해야겠다 생각을 해본적이 없었다.

H-Index
논문 n편, h번 이상 인용된 논문이 h개 이상
나머지 논문이 h번 이하인용 => h의 최대값

 

3. 문제 풀이

풀이 (1) 100/100: deque 사용

우선은 List를 오름차순으로 정렬하고 생각을 해봤다.

[0, 1, 3, 5, 6]
0 -> 0
0, 1 -> 1
0,1,3 -> 1
0,1,3,5 -> 2
0,1,3,5,6 -> 3

이렇게 할 경우 조금 복잡하게 생각이 들어서 반대로 내림차순 정렬을 하고 다시 생각해봤다.

[6, 5, 3, 1, 0]
(개수, 최솟값) 의 쌍으로 본다면
6 -> 1 (1,6)
6,5->2 (2,5)
6,5,3->3 (3,3)
6,5,3,1->3  => 1이 들어와봐야 H-Index는 변하지 않는다.
6,5,3,1,0->3 => 마찬가지로 0은 영향을 주지 않는다.

 

def solution(citations):
    
    
    sorted_citations = sorted(citations, reverse=True)

    h_idx = 0
    tmp = []
    for cnt, citation in enumerate(sorted_citations):
        tmp.append(citation)
        
        if cnt+1 <= min(tmp):
            h_idx = cnt+1
    
    return h_idx

테스트 1 〉	통과 (4.11ms, 10MB)
테스트 2 〉	통과 (5.63ms, 9.99MB)
테스트 3 〉	통과 (4.28ms, 10MB)
테스트 4 〉	통과 (3.35ms, 10.1MB)
테스트 5 〉	통과 (5.31ms, 9.94MB)
테스트 6 〉	통과 (11.32ms, 10.1MB)
테스트 7 〉	통과 (1.21ms, 10.2MB)
테스트 8 〉	통과 (0.05ms, 9.97MB)
테스트 9 〉	통과 (0.30ms, 10MB)
테스트 10 〉	통과 (1.48ms, 10.2MB)
테스트 11 〉	통과 (11.16ms, 10.1MB)
테스트 12 〉	통과 (0.24ms, 10MB)
테스트 13 〉	통과 (6.42ms, 10.2MB)
테스트 14 〉	통과 (8.09ms, 10MB)
테스트 15 〉	통과 (6.71ms, 10.1MB)
테스트 16 〉	통과 (0.01ms, 10.2MB)

sorted() 한번 쓰면서 O(n)을 1회

그 다음 for문 1회를 돌면서 O(n)을 1회로 그렇게 복잡하지 않게 정리했다.

 

4. 주요 코드 및 정리