iyOmSd/Title: Algorithm풀이

[Swift Algorithm] 42747 H-Index (프로그래머스)

냄수 2021. 3. 19. 17:16
반응형

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

 

코딩테스트 연습 - H-Index

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표

programmers.co.kr

풀이방법

문제는 짧지만 개념이 좀 어려운 문제에요

 

발표한 논문 n편중

h번이상 인용된 논문이 h편이상이고 나머지논문이 h번이하 인용되면 h의 최댓값이 답이다...

 

머라는거야... 헷갈리네요 ㅎㅎ

 

[3, 0, 6, 1, 5] 배열이있다면

우선 보기좋게 정렬해볼게요

 

[6, 5, 3, 1 ,0] 이 될거고

index와 인용된 논문을 비교해줄거에요

h번 이상 인용된 논문을 찾아갈건데 h는 1부터시작할거에요

0부터시작하면 어짜피 모든 배열요소의 수만큼 되기때문에 의미가없죠

따라서 h는 i+1이 될거에요

hIndex는 값이아닌 Index이기때문에 이점 유의하시구요

 

i: 0, value: 6

h: i+1 = 1

1번이상 인용된 논문이 1개이상이 성립하네요

 

i: 1, value: 5

h: 2

2번이상 인용된 논문이 2개이상 성립하죠

 

i: 2, value: 3

h: 3

3번이상 인용된 논문이 3개이상 성립하구요

 

i: 3, value: 1

h: 4

4번이상 인용된 논문이 4개이상 성립하지않아요 

값이 1이기때문에 조건에 맞지않게 되었네요

 

여기서 원리가 느껴지시나요?

 

내림차순으로 정렬된 배열의 처음부터 비교하면서

배열의 해당 값과 h를 비교해서 값이 작아지는 그 곳의 i값이 hIndex의 최댓값이에요

 

'나머지논문이 h번이하 인용되면' 조건문은 확인하지 않아도 되는 부분이에요

왜냐하면

h는 최댓값이기때문에

정렬되있는 배열을 탐색하며

최댓값의 값을 찾게되면 나머지논문은 자연스럽게 h번이하 인용되는 논문이 남죠

 

h > value 조건문으로 검사를해서 처리를 할 때

예외케이스로

인덱스보다 전부높은 인용된 수의 배열이 올 수 있는데

예를들어 [10, 11, 12, 13] 같은 경우죠

 

이런 경우만 잘 처리해주면 잘 동작해요

 

private func solutionP42747(_ citations:[Int]) -> Int {
    let citations = citations.sorted(by: >)
    var result = -1
    for i in citations.indices {
        let value = citations[i]
        let h = i+1
        
        if h > value {
            result = i
            break
        }
    }
    if result == -1 {
        return citations.count
    }
    print(citations)
    print(result)
    return result
}

 

반응형