[Programmers] H-Index (Swift)

문제 : 

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

코딩테스트 연습 - H-Index

 

1. 문제 이해하기

• 해당 문제는 이해만 제대로 했다면 어렵지 않게 풀이할 수 있습니다.
• 어떤 과학자가 발표한 논문 n 편 중, 자연수로 시작하는 인덱스 h를 기준으로 h이상 인용된 논문이 h 편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값 리턴
• 예시로 더 자세하게 설명하겠습니다.

 

2. 문제 풀이 생각하기

1. 처음에는 문제를 이해하는데 애를 먹었습니다. 이유는 인덱스가 1부터 시작하는지 몰랐고, citations를 왜 내림차순 정렬해야 하는지 이해하지 못했었습니다.
2. citations 내림차순 정렬
3. while을 돌면서 index보다 citations[index]가 작거나 같으면 해당 인덱스를 리턴
4. 전체 citations의 크기를 넘어가면 citations 크기를 리턴

 

간단한 예시를 들어보겠습니다.

[10, 8, 5, 4, 3], [10, 8, 5, 3, 3] 두 개의 citations를 비교해보겠습니다. (파란색 숫자는 인덱스입니다.)

[10, 8, 5, 4, 3]의 경우, 인덱스 4를 기준으로 4 이상인 숫자가 4개(10, 8, 5, 4), 4 이하인 숫자가 1개(3)

하지만, 인덱스 5 이상인 숫자는 4개(5개 미만)가 되기 때문에 최댓값이 4가 됩니다.

 

[10, 8, 5, 3, 3]의 경우, 인덱스 3을 기준으로 3 이상인 숫자가 3개(10, 8, 5), 3 이하의 숫자가 2개(3, 3)

하지만, 인덱스 4 이상인 숫자는 3개(4개 미만)가 되기 때문에 최댓값이 3이 됩니다.

 

실제로 답을 구할 때는 인덱스를 0부터 시작하고 해당 인덱스의 값이 인덱스보다 작거나 같을 때 해당 인덱스를 출력합니다.

참고로 오름차순 정렬을 하게 되면 해당 인덱스보다 작은 값의 개수가 몇 개인지 바로 알 수 없습니다. ex) [0,0,0,1,1,1,4,4,4]

 

h-index를 구하는 식입니다. (출처: 위키백과)

 

3. 차근차근 구현하기

import Foundation

func solution(_ citations:[Int]) -> Int {
    let citations = citations.sorted(by: >)
    var index = -1
    var ans = 0
        
    while true {
        index += 1
        if index >= citations.count {
            return citations.count
        }
        
        if index >= citations[index] {
            ans = index
            break
        }
    }
    
    return ans
}

 

4. 피드백

• 문제를 좀 더 빨리 이해할 수 있도록 계속해서 훈련하자!