프로그래머스 - h-Index(Swift)

프로그래머스 - h-Index(Swift)

 

 

 문제 설명

 

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

프로그래머스

 

 

 나의 풀이

 

0부터 arr.count까지 h-index가 될 수 있는 수들을 탐색하면서 filter값으로 maxIdx를 계속 변화를 시켰다.

하지만 이 풀이는 문제 조건이 커지면 실패하는 풀이기에 다른 사람들의 코드를 보면서 좀 더 효율적인 것을 찾았다.

 

import Foundation

func solution(_ citations:[Int]) -> Int {
    var arr = citations.sorted(by: <)
    var maxIdx = 0
    for x in Array(0...arr.count) {
        let upperIdx = arr.filter{ $0 >= x }.count
        let lowerIdx = arr.filter{ $0 < x }.count
        if upperIdx >= x && lowerIdx <= x {
            maxIdx = x
        }
    }
    return maxIdx
}

 

 

 

 다른 사람의 풀이

 

풀이를 이해하는데 조금 시간이 걸렸지만 한 번 이해하면 좋은 풀이라는 걸 알 수 있다.

 

먼저 문제의 예시인 [0, 1, 3, 5, 6]을 내림차순으로 정렬해보자. -> [6, 5, 3, 1, 0]

인덱스를 1씩 증가시킬 것인데 이때 인덱스는 h-index이다.

첫번째로 h-index가 1일때 배열의 첫번째 값보다 작거나 같다면 h-index를 1로 설정할 수 있다. 왜냐하면 문제는 h번이상 인용된 논문의 수가 h개 이상이고, 나머지 논문이 h번 이하 인용이 되는 것인데, 배열의 첫번째 원소인 6은 1번이상 인용되면서 1개이상이고 나머지 논문들은 1번 이하로 인용이 되었기 때문이다.

 

두번째를 보면 h-index가 2일때 배열의 원소인 5와 비교하게되고 이 또한 2번이상 인용된 것이 2개 이상이기 때문에(처음 6인 원소가 1개 이번에 체크한 것 포함해서 2개) h-index가 2가 된다. 

나머지 논문이 h번 이하 인용되었다면의 조건은 최대값을 찾은 후에 나머지 논문들은 자연스럽게 h번 이하의 논문들만 담기기 때문에 신경쓰지 않아도 된다.

 

이를 반복하면서 배열의 현재 값과 증가하는 index값을 비교하면서 배열의 값이 작아지는 시점이 h-index의 최대값이 된다.

 

import Foundation

func solution(_ citations:[Int]) -> Int {
    var citations = citations.sorted(by: >)
    var result = 0
    
    for i in 0..<citations.count {
        //이 if문이 참이라면 현재 h번 이상 인용된 논문이 h편 이상인 것
        if i+1 <= citations[i] {
            result = i+1
        }else {
            break
        }    
    }
    return result
}

 

 피드백

 

증가하는 인덱스 = 논문에 인용된 개수로 문제를 만드는 것이 핵심