[Swift][프로그래머스][정렬] H-Index

요구능력

정렬 활용

 

문제풀이

나는 처음에 citations에 있는 인용수가 h-Index에 들어가는건줄 알고 꽤나 오랜시간 삽질을 했다.

문제를 잘 이해하면 h-Index는 최대 citations의 개수만큼 나온다.

문제에서 논문 n편 중 h번이상 인용된 논문이 h편 이상이고,

나머지가 h번 이하 인용되었다면 h의 최대값이 h-Index라고한다.

 

바로 예제로 설명을 해보자.

[3, 0, 6, 1, 5]가 있다.

 

h가 1인경우를 살펴보자.

H-Index가 1이면 논문 5편중 1번이상 인용된 논문이 1편 이상이고,

나머지가 1번 이하 인용되는가?

1번이상 인용된 논문 [3, 6, 1, 5]이 있고 나머지[0]은 1번이하 이므로 인용된다.

 

h가 2인경우를 살펴보자.

H-Index가 2이면 논문 5편중 2번이상 인용된 논문이 2편 이상이고,

나머지가 2번 이하 인용되는가?

2번이상 인용된 논문 [3, 6, 5]이 있고 나머지[0, 1]은 2번이하 이므로 인용된다.

 

h가 3인경우를 살펴보자.

H-Index가 3이면 논문 5편중 3번이상 인용된 논문이 3편 이상이고,

나머지가 3번 이하 인용되는가?

3번이상 인용된 논문 [3, 6, 5]이 있고 나머지[0, 1]은 3번이하 이므로 인용된다.

 

h가 4인경우를 살펴보자.

H-Index가 4이면 논문 5편중 4번이상 인용된 논문이 4편 이상이고,

나머지가 4번 이하 인용되는가?

4번이상 인용된 논문 [6, 5]이 있고 나머지[0, 1, 3]은 안된다.

인용된 논문이 4편이 되지않고 2편이다.

 

h가 5인경우를 살펴보자.

H-Index가 5이면 논문 5편중 5번이상 인용된 논문이 5편 이상이고,

나머지가 5번 이하 인용되는가?

5번이상 인용된 논문 [6, 5]이 있고 나머지[0, 1, 3]은 안된다.

인용된 논문이 5편이 되지않고 2편이다.

 

이렇게 되는데 물론 브루트포스로 이것저것 끼워넣어서도 풀 수 있을것이다.

하지만, 문제에서 논문의 수가 1000편까지 갈 수 있다고 했으므로, for문 2개만 갖다써도 O(n^2)이 되서 최악의 경우 1000000가지 경우를 봐야하고 시간초과가 발생할 것이다.

 

그래서 정렬을 사용해 줄 생각을 해야한다.

이유는 정렬을 해주면 H-Index를 구하기가 꽤나 쉬워진다.

정렬의 성질을 이용하자.

예시로 n이 6이고 h가 6인경우를 봐보자.

[0, 1, 2, 3, 4, 5]

h가 6인 경우가 될까?

 

안된다.

여기에 문제의 조건을 그대로 갖다붙여보자.

논문 6편중 6번이상 인용된 논문이 6편이상이고 나머지가 6번이하 인용되어야한다.

그러면, 논문이 총 6편이니까 전부 다 6번이상 인용되어야만

인용된 논문이 6편이상이다.

 

오름차순 정렬의 특성상 h가 6인경우는 맨앞에 와있는 가장 작은수가 6번이상 인용되야 조건이 성립된다.

그래서 우리는 n번의 반복만으로 결과값을 구할 수 있다.

 

오름차순을 해놨으니 맨앞부터 탐색을 시작하면

H-Index는 n - i로 두면 n = 6일때 H-Index는 6, 5, 4, 3, ... 이렇게 갈것이고 H-Index의 값과 현재 sorted[i](오름차순 정렬된 citations)와 값을 비교해주면 된다.

 

참고)

let result = 0

return result 이 부분처리를 안해주면 테스트케이스 16번에서 걸리게된다.

[0]을 넣어보면 알겠지만, 1개의 논문이 인용횟수가 0이면 h는 1조차 될 수 없다.

위에서 우리는 h_index를 1까지만 봤기 때문에 따로 처리를 해준것이다.

h_index를 1까지만 보는 이유는 0까지 보려면 0..<n이 아닌 0...n이 되어야하는데,

이렇게되면 sorted[n]이 들어가서 index out of range가 발생하게된다.

따라서 1까지만 보고 0은 따로 처리해준것이다.

 

후기

문제가 엄청 복잡하다..

알고나면 쉽지만 어려운문제..

코드

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