본문 바로가기
Algorithm/Programmers

[프로그래머스] 코딩테스트 고득점 Kit > H-Index

by du.it.ddu 2020. 3. 7.
반응형

# 문제

# 문제 접근

H-Index라는 개념이 굉장히 헷갈리는 문제다.

우선 N은 논문의 수인 citations의 길이다. 즉, 예제에서는 5다.

h를 1 부터 증가시켜 가며 천천히 생각 해 보자.

1. h = 1 인 경우, 5편 중 1번 이상 인용된 논문은 [1, 3, 5, 6]로 4개이다. 그리고 나머지 논문 [0]은 1번 이하 인용되었다.

2. h = 2 인 경우, 5편 중 2번 이상 인용된 논문은 [3, 5, 6] 로 3개이다. 그리고 나머지 논문 [0, 1] 은 2번 이하 인용되었다.

3. h = 3인 경우, 5편 중 3번 이상 인용된 논문은 [3, 5, 6] 로 3개이다. 그리고 나머니 논문 [0, 1]은 3번 이하 인용되었다.

위에서 3번 케이스의 경우, N편(5) 중 h번(3) 이상 인용된 논문이 h편(3) 이고 나머지 논문이 h번(3) 이하로 인용되었으므로 답이 된다.

그럼 다음 케이스를 보자.

[20, 19, 18, 1] 의 예시를 보자.

이 경우도 답은 3이다.

이유는 4편 중 3번 이상 인용된 논문이 [18, 19, 20] 으로 3편 이고, 나머지 논문인 [1] 이 3번 이하로 인용되었기 때문이다.

즉, 정답은 리스트의 값들 중 하나가 아니며 조건을 만족하는 어떤 숫자를 찾아야 한다는 것이다.

# 문제 풀이

다시 생각 해 보면, N편 중 h번 이상인 논문이 h편 이상이라는 것은 h가 N편 이하의 값으로 존재한다는 것이다. 이는 리스트의 인덱스 값과 연관 지을 수 있다.

또한 N편 중 h번 이상인 논문이 h편 이려면 리스트를 역으로 내림차순으로 정렬했을 때 현재의 인용 횟수 이상인 논문들이 h-1개 이상 존재한다는 것이다.

즉, 리스트를 [6, 5, 3, 1, 0]와 같이 정렬했을 때를 생각해보자.

1. i = 0일 때, h = 6이다. 5편 중 인용된 횟수가 6번 이상인 논문이 6편 이상일 수 있는가? 앞의 요소가 0개 이므로 불가능하다.

2. i = 1일 때, h = 5이다. 5편 중 인용된 횟수가 5번 이상인 논문이 5편 이상일 수 있는가? 앞의 요소가 1개 이므로 불가능하다.

3. i = 2일 때, h = 3이다. 5편 중 인용된 횟수가 3번 이상인 논문이 3편 이상일 수 있는가? 앞의 요소가 2개 이므로 가능하다.

이제 코드를 짜보자. 코드는 굉장히 짧다.

# 코드 작성

def solution(citations):

    N = len(citations)
    # 리스트를 내림차순으로 정렬한다.
    citations.sort(reverse = True)
    
    for i in range(N) :
    	# 조건을 만족하는 i를 찾아 리턴한다.
        if citations[i] <= i:
            return i
    
    # 위에서 반환하지 못하고 루프를 탈출한 것은 H-Index = N인 경우이다.
    return N

 

 * 본 문제의 출처는 프로그래머스(https://programmers.co.kr/) 입니다. 문제가 될 시 삭제하겠습니다.

반응형