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

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42747

코딩테스트 연습 - H-Index

 

 

풀이

 

def solution(citations):
    citations.sort(reverse = True)
    
    for index in range(len(citations)):
        subscribe_count = citations[index]
        if index + 1 > subscribe_count:
            return  index
        
    return len(citations)

 

일단 문제에서 필요없는 정보 다 빼고 이해를 해야하는데,

h번 이상 인용된 논문이 h편 이상이면 H-Index가 h이다. h를 구해라. 이것만 알면 됨.

(값이 h 이상인 성분이 h개 이상 있니?)

그래서 로직은 다음과 같다.

 

● 인용 횟수는 나와있는 값이니까 h편 이상인가?를 판단하는 것이 핵심

 

1. for문으로 index를 사용하여 하나씩 참조하면 내가 인용 횟수를 확인한 논문의 수와(몇 편 = index+1)

   인용 횟수가 얼마인가?를 확인 가능함.

2. 즉, 내림차순으로 citations 리스트를 정렬하고 index를 증가시켜가면서 for문으로 인용횟수를 확인하는데

     index + 1보다 인용 횟수가 작은 곳이 판단 지점

3. 만약 for문을 탈출했다면 인용 횟수의 최저값이 확인한 논문 수보다 많다는 의미이므로 return len(citations)

 

---

 

시간 복잡도

 

시간 복잡도는 for문이 한 번 슥 도니깐 O(N)이다.

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

위에서도 적어놨는데 

 

● 인용 횟수는 나와있는 값이니까 h편 이상인가?를 판단하는 것이 핵심

 

코딩하다가 성분 값과 인덱스 중에 뭘 기준으로 해야할지 헷갈려서 한 번 틀렸다.

보니까 내부 성분은 바뀌지 않는 값이고 index만 계속 증가하면서 바뀌기 때문에 index가 기준이다.

 

H-Index라는 개념을 이해하는데 오래 걸렸지 문제 자체는 아이디어만 떠올리면 간단히 풀 수 있는 문제였다.

그리고 놀랍게도 지금 진행 중인 구글 킥스타트에서 굉장히 유사한 문제가 나온다.