[프로그래머스] H-Index with Swift, Python

• 연습문제
• H-Index
• Level 2

 

문제

• 발표한 논문 n편 중, 
• h번 이상 인용된 논문이 h편 이상이고 
• 나머지 논문이 h번 이하 인용되었다면 
• h의 최댓값이 이 과학자의 H-Index

 

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

 

예.

[3, 0, 6, 1, 5]

→ 3

이 과학자가 발표한 논문의 수는 5편이고, 

그 중 3편의 논문은 3회 이상 인용되었습니다. 

그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 

이 과학자의 H-Index는 3

 

Idea

• 논문을 인용 횟수에 따라 정렬하기 (그 이유는 아래 풀이 참고. 사실 이 문제는 정렬하지 않아도 풀 수는 있음!)
• 논문의 개수를 기준으로 확인하는데 (인용 가능한 횟수보다 논문의 개수가 더 적기 때문) 
• 논문 편수(0 ~ n)만큼 인용된 논문의 수를 구하면 됨

 

Code

Swift

• 첫번째 중요한 포인트는 h가 나올 수 있는 범위는 0~n 이라는 것이다. 따라서 주어지는 citation값을 기준으로 h값을 찾는 것이 아니라 논문의 개수를 기준으로 해야한다.
• 그 다음 중요한 포인트는 “h번 이상 인용된 논문이 h편 이상” 이라는 것이다.
• 동일한 인용횟수를 가진 논문이 있을 수 있기 때문에 반드시 고려해야 한다.
• 처음에 h번 이상 인용된 논문이 무조건 h편이라고 생각하고 풀었더니 오류가 있었다.

 

예로. [3, 4, 5, 8, 10] 이라는 인용 횟수가 주어질 때,

이 경우는 당연히 H-Index가 4가 된다.

하지만 [3, 3, 5, 8, 10] 이라는 인용 횟수가 주어지고, h편 이상이 아닌 h편이라고 생각한다면 답이 나올 수 없다.

왜냐하면 5번 이상 인용된 논문 개수는 3, 4번이상 인용된 논문 개수는 3, 3번이상 인용된 논문 개수는 5이기 때문이다.

하지만 h편 이상이라는 조건이 포함되어 있기 때문에 "3번이상 인용된 논문은 3편 이상"이라는 말이 성립될 수 있다.

 

• 첫번째 풀이는 문제의 의미를 그대로 코드로 옮겨 풀었다.
• 결과적으로 정렬을 하지 않아도 구할 수 있지만 논문 수가 많아진다면 시간 초과가 발생하기 딱 좋은 풀이다.
• 정답은 나오지만 다음 풀이에 비해 시간이 오래걸린다.

import Foundation

func solution_1(_ citations:[Int]) -> Int {
    
    let n = citations.count
    
    for h in (0...n).reversed() {
        if h <= citations.filter { $0 >= h }.count {
            return h
        }
    }
    
    return 0
}

 

• 두번째 풀이는 문제를 살짝 의역하여 푼 느낌이다.
• citation의 인덱스가 0 ~ n-1이므로 그 값을 사용하여 h 값을 정하게 된다.
• 이 풀이에서는 정렬이 중요한 요소로 작용한다.

 

예를 들어 [3, 5, 10, 14, 15]이며 n == 5, i가 (0...n-1) 일때,

i : 1, n-i (h) : 4 → citations[1] 값이 h(n-i), 즉 4이상인지 판단

→ 만약 1번째 값이 h(n-i) 값 이상이라면, 현재 정렬된 상태이므로 나머지 값도 모두 h 이상이 된다.

→ [3, 5, 10, 14, 15]

→ 따라서 자동으로 h(n-i)편 이상이 h번 이상 인용되었다는 것을 알 수 있다.

 

설령 예시가 [3, 3, 5, 8, 10] 이라도

[3, 3, 5, 8, 10]

i : 1, n-i : 4 → citations[1] 값은 3 이기 때문에 해당되지 않지만 (1번째 값이 4회 이상 인용되지 않았기 때문에)

[3, 3, 5, 8, 10]

i : 2, n-i : 3 → citations[2] 값은 5 이므로 나머지 3 편은 모두 해당된다.(2번째 값이 3회 이상 인용되었다.) 그 앞의 값 또한 3 이상이지만 h편 “이상” 이기 때문에 그 앞의 논문이 h번 이상 인용되었는지 확인할 필요가 없다.

 

import Foundation

func solution_2(_ citations:[Int]) -> Int {
    
    let citations = citations.sorted()
    let n = citations.count
    
    for i in 0..<n {
        if n - i <= citations[i] {
            return n-i
        }
    }
    
    return 0
}

 

Python

• 위의 두번째 풀이와 동일한 코드

def solution(citations):
    
    citations.sort()
    n = len(citations)
        
    for i in range(n):
        if n-i <= citations[i]:
            return n-i
        
    return 0