[알고리즘][Swift]#5. H-Index

안녕하세요! caution 입니다. '-'

알고리즘 풀이 5번째 시간입니다~ 우왕~ 벌써 2018년이 얼마 안 남았네요!!

연말이라고 뭐 다를 거 있겠습니까, 저야 뭐 코딩하겠죠 하하.....

진짜 내일이 크리스마스네요~ 모두들 메리크리스마스! 

오늘의 문제는 Level 2. H-Index 입니다.  

문제 설명

---

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

 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h가 이 과학자의 H-Index입니다.

 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

---

과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.

논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

도대체 H-Index가 뭐야! 라고 위키를 열었다가 영어크리에 창을 닫았습니다... 문제를 읽고 나서도 완전히 이해하는 데 좀 시간이 걸렸던 문제에요. 이럴 땐 테스트 케이스를 많이 만들어 보는 게 좋아요!

먼저 주어진 입출력 예를 보겠습니다.

입출력 예

---

citations : [3, 0, 6, 1, 5]             H-Index : 3

 

 이 과학자는 총 5편의 논문을 썻고, 그 중 3회 이상 인용된 논문이 3편 이상이고, 나머지 논문들은 3회 이하 인용되었기 때문에 H-Index는 3이 됩니다. 하지만 여전히 알쏭달쏭하시죠? 테스트 케이스를 몇 개 더 추가해봅시다. 이 문제에서 발표한 논문의 수는 1편 이상이라고 이미 제한사항에 기재되어있기 때문에 입력값이 empty 일 경우는 제외하였습니다.

 

테스트 케이스

---

case 1) citations : [10, 100]                   H-Index : 2

case 2)  citations : [6, 6, 6, 6, 6, 6]        H-Index : 6

case 3) citations : [2, 2, 2]                     H-Index : 2

 

 case 1을 보시죠. 이 과학자는 총 2편의 논문을 썼고 하나는 10회, 하나는 100회 인용되었습니다. 이때 H-Index가 10이 아닐까 라고 생각할 수 있지만, 그러려면 과학자는 총 10번 이상 인용된 논문이 10개 이상 있어야 합니다. 그러므로 H-Index는 2 입니다. 이 과학자의 논문은 2회 이상 인용된 논문이 2편 이상이고, 나머지 논문들은 2회 이하 인용되었습니다. 비록 나머지 논문의 수가 0이지만, 상관없습니다. 조건만 만족하면 되니까요. case 2에서는 과학자의 논문는 6회 이상 인용된 논문이 6편 이상이고, 나머지 논문들은 6회 이하 인용되었습니다. 위의 케이스들에는 논문들의 수가 H-Index 가 되었습니다.

반면 논문들의 수와는 다른 결과가 나오기도 합니다. case 2과 case 3은 모두 같은 인용횟수를 가지는 논문들로 구성되어 있습니다. case 3에서 과학자의 논문은 2회 이상 인용된 논문이 2편 이상이고, 나머지 논문들은 2회 이하 인용되었습니다. case 3에서 논문의 개수는 3개 이지만, 3회 이상 인용된 논문은 없기 때문에 2가 H-Index가 되게 됩니다.

 자 여기서 H-Index에 대해 되짚어 봅시다. 결국 H-Index 는 논문이 10,000회 인용됐더라도 논문의 총 수량보다 크지 않습니다. 반면 [0,0,0,0, ... , 0]의 케이스에는 H-Index는 0이 되어야 합니다. 이제 H-Index 는 0 에서 1,000 까지의 범위를 가지겠네요.

 본격적으로 문제를 풀어봅시다. 주어진 입출력 예인 [3,0,6,1,5] 에서 H-Index를 구하려면 어떻게 해야할까요?

for 문을 돌면서, 주어진 수보다 크거나 작은 경우의 수를 각각 구한 다음, 조건에 맞는지 확인하는 건 어떨까요? 충분히 가능하지만, 이 경우 for 문을 돌면서 O(n), 주어진 수보다 크거나 작은 경우를 매번 구해야 하는데 O(n) , 총 (n2)의 시간복잡도가 발생합니다. 논문의 수가 커질수록, 너무 많은 시간이 소모됩니다. 이중 for문은 언제나 좋은 선택지가 아니죠.

 자 다시 프로그래머스 문제 화면을 살펴봅시다. 왼쪽 상단에 보면 이 문제는 정렬문제라고 알려주네요. 문제안에 답이 있다! 

한 번쯤 정렬을 시도해보는 것도 좋겠네요. 그럼 어떤 정렬이 유효할까요? 우리는 H-Index 를 찾습니다. citations 가 순차적으로 정렬되어 있다면, 이 배열의 Index가 H-Index 를 대변할 수 있습니다. [3,0,6,1,5] 로 해보죠!

[3,0,6,1,5] 

> 내림차순 배열 : [6,5,3,1,0]

> index 0 , num 6      >> 인용 횟수가 0 이상인 논문의 수 : 5, 인용 횟수가 0 이하인 논문의 수 : 1 

> index 1, num 5        >> 인용 횟수가 1 이상인 논문의 수 : 4, 인용 횟수가 1 이하인 논문의 수 : 2

> index 2, num 3       >> 인용 횟수가 2 이상인 논문의 수 : 3, 인용 횟수가 2 이하인 논문의 수 : 2

> index 3, num 1       >> 인용 횟수가 3 이상인 논문의 수 : 3, 인용 횟수가 2 이하인 논문의 수 : 3

 index 3에서, 처음으로 조건을 만족하며, 이때 index 값이 num 보다 커집니다. 이는 현재 index의 앞에 있는 논문들은 이미 그 인용횟수가 index보다 크다는 것을 의미합니다. 그래서 "인용횟수가 h이상인" 조건을 만족합니다. 또한 우리는 내림차순으로 정렬했기 때문에, 나머지 논문들은 모두 "인용횟수가 h 보다 작다" 는 조건을 만족합니다.

 위의 논리를 기준으로 작성된 코드입니다.

func solution(_ citations:[Int]) -> Int {

    let sorted = citations.sorted(by: >)

    for i in 0..<sorted.count {

        if i >= sorted[i] {

            return i

        }

    }

    return 0

}

 먼저 주어진 배열을 내림차순으로 소팅한 배열을 만들었고, 이 배열을 돌면서 index 값이 인용 횟수보다 크거나 같은 지점을 찾습니다. (왜냐하면 주어진 조건이 인용 회수가 초과가 아닌 h번 이상이기 때문입니다.)지점을 찾았다면 해당 index 값을 넘겨줍니다.

 자, 코드를 다 짠 것 같지만 이때 실행해보면?

 앗,,, 앞서 추가했던 테스트 케이스 3개 중 2개의 케이스에서 실패가 발생했습니다. 왤까요? 우리가 작성한 코드에 따르면 i >= sorted[i] 여야 하는데, 테스트 2와 테스트 4의 경우, 이 조건에 해당하지 않습니다. 인용 횟수에 비해 논문의 수가 너무 작기 때문에, for문을 다 돌아도 주어진 조건에 맞는 결과를 찾을 수 없는 거죠. 이 경우에는 H-Index는, 논문의 수가 되게 됩니다. 

 그럼 코드를 수정하고, 실행시켜봅시다.

func solution(_ citations:[Int]) -> Int {

    let sorted = citations.sorted(by: >)

    for i in 0..<sorted.count {

        if i >= sorted[i] {

            return i

        }

    }

    return sorted.count

}

짠! 이제 다시 실행시켜보면?

 모든 테스트를 통과했네요! 이제 코드를 채점해봅시다! 

 저는 이 코드로 문제를 해결했어요! +_+ 14점을 주네요! 높은건지 낮은건지 도통 알수가 없네요... 그래도 처음 구상했던 방법보단 최대 시간복잡도가 2O(n) 이니까 많이 줄어들었네요 ㅠ_ㅠ

 도움이 되셨기를 바라요! 이 글을 작성하는 동안 이브가 끝났답니다!!!!!!!!!

 메리 크리스마스!!!!!!!