[프로그래머스] level2 : H-Index 구하기

1. 문제 설명

• 문제 설명 보러가기

2. 문제 해석 

이 문제는 이해하기가 너무 어려웠다. 이럴 경우 예제를 먼저 보고 값을 문제에 대입해보자.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고...

여기서 h가 H-Index가 된다. 아래는 내가 추가한 테스트케이스 들이다. 

문제번호	주어진 논문 (input)	return
1	[3, 0, 6, 1, 5]	3
2	[5, 5, 2]	2
3	[1, 1, 1]	1
4	[0, 0, 0]	0
5	[0, 0, 0, 1]	1
6	[4, 4, 4, 4]	4
7	[4, 20, 35, 60, 70]	4

여기서의 return값이 이해 되는가? 만약 안 된다면 예제를 보고 값을 문제에 대입해보자.

논문은 n편이 주어지는데, 1번의 경우 논문 갯수는 [3,0,6,1,5]로 총 5편이다. 각각 3번, 0번, 6번, 1번, 5번 인용되었다.

"논문 5편 중 3번 이상 인용된 논문 3편 이상이고.." => true

"논문 5편 중 0번 이상 인용된 논문이 3편 이상이고.." => true

"논문 5편 중 6번 이상 인용된 논문이 6편 이상이고.." => false

"논문 5편 중 1번 이상 인용된 논문이 1편 이상이고.." => true

"논문 5편 중 5번 이상 인용된 논문이 5편 이상이고.." => false

true인 값을 보면 3, 0, 1 이 나온다. H-Index는 값이 클 수록 좋은 치수다. 문제에서도 최댓값을 구하라고 되어있다. 그러므로 답은 3이다.

값을 대입해보면 h의 최댓값은 n이라는 것을 알 수 있다.

즉 h집합은 n 이하인 양의 정수 && h번 이상 인용된 논문이 h편 이상인 경우들이고 이 h집합에서의 최댓값이 H-Index이다.

이것을 어떻게 구할 수 있을까?

 

3. 문제 풀이

• 키포인트
  • 이 문제가 '정렬' 카테고리에 있는 문제임을 기억하자
  • 성능을 위해 최소한의 loop만 돌 수 있도록 만들면 좋다

내 처음 풀이인 성능 나쁜 버전부터 살펴보자.

function solution(citations) {
   const sorted = citations.sort((a,b) => b-a)
   const filtered = sorted.filter((item, idx) => item >= idx + 1)
   return filtered.length;
}

1. 문제풀이
   1. 받은 배열을 큰 숫자 순으로 정렬하여 sorted에 넣는다. => 큰 값 부터 사용하기 위해
   2. sorted에서 각각의 값이 idx + 1 보다 크거나 같은 값만 필터한다.
   3. 이렇게 하면 filtered.length가 'h번 이상 인용된 논문이 h번 이상이고..'를 만족하는 최댓값을 구할 수 있다.

---

성능을 개선한 버전을 살펴보자.

위 풀이에서는 sort로 오름차순 정렬을 했음에도 loop를 처음부터 끝까지 돌아야 했다.

item >= idx + 1 = false 라면 loop을 멈춰도 되는데도 말이다. 그래서 filter에서 for문으로 바꿔주었다.

function solution(citations) {
    const sorted = citations.sort((a,b) =>b-a)
    for(let i=0; i < sorted.length; i++){
        if(!(sorted[i] >= i + 1)) return i
    }
    return citations.length
}