[leetcode][275] H-Index II

문제 : https://leetcode.com/problems/h-index-ii/

---

오름차순으로 정렬된 양의 정수 배열이 주어진다고 하자. (let, 배열 크기 = N)

이 배열은 논문들이고, 각 배열 값은 i번째 논문이 몇 개의 논문을 인용했는지를 나타낸다. 즉, arr[2] = 3이라면 2번째 논문은 3개의 논문을 인용하여 작성되었음을 의미한다.

N개의 논문중 h개의 논문이 h개 이상의 논문을 인용하고 N-h개는 h개 이하를 인용하는 경우 h-인덱스라고 한다.

배열의 가능한 h-인덱스 값 중 최대값을 구해라.

---

이분 탐색으로 풀어보자. 어쨌든 h의 범위는 논문의 개수이다.

l, r 은 배열의 시작인덱스, 종료인덱스로 잡자.

m = (l+r)/2이다.

h = N - m라고 하고 h가 정답이 가능한지 판단한다.

문제 초반에 정렬된 배열이 주어졌다고 했으므로 citations[m] 이 N - m보다 같거나 크다면 정답이 가능한 경우다.

이렇게 말하면 잘 이해가 안되는데 예를 들어보자.

[0,1,3,5,6] 이고 N = 5, m = 3, citations[3] = 5을 판단해보자. m이 3일때를 체크하는 거다.

N-m은 m번째 논문이 인용한 논문 수보다 같거나 많은 갯수의 논문을 인용한 경우가 몇개인지를 의미한다. 이경우는 2이다.

citations[3]은 5이다. 즉, h = 2가 정답이 가능한지 보는데, 기준점이 되는 m번째 논문의 인용 수가 h보다 같거나 크다면 정답이 가능하다.

citations[m]이 h보다 같거나 크다면 h개의 citations[m], citations[m+1] ... citations[N]들도 h보다 같거나 크다는 조건을 만족하기 때문이다. 

여기서 생각해볼건 citations[m]이 h보다 같거나 크다면 citations[m-1]도 h보다 같거나 클수도 있지 않은가? 이다.

citations[m-1]

i) h보다 작은 경우 : h개의 논문이 h개 이상의 논문을 인용하고 나머지 N-h개는 h개 미만의 논문을 인용하므로 h-인덱스 조건을 만족한다.

ii) h와 같은 경우 : h개의 논문이 h개 이상의 논문을 인용하고 나머지 N-h개는 h개 이하의 논문을 인용하므로 h-인덱스 조건을 만족한다.

iii) h보다 큰 경우 : 이 경우는 이분 탐색 범위에 m-1 이 포함되므로 정답이 가능한지 나중에 판단될 것이다. 즉, 지금은 일단 넘어가도 된다. 

 

정답이 가능한 경우 정답 변수를 h(= N-m)로 갱신하고 r을 m-1로 갱신한다. 

정답이 불가능한 경우 l을 m+1로 갱신한다.

이를 l > r 가 될때까지 반복한다.

 

시간복잡도는 O(logN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/275.%20H-Index%20II.cpp

---

오늘 처음 알았는데 최적화 문제를 이분탐색으로 변경해서 푸는 걸 parametric search 라고 한다.

즉, 최소, 최대를 구하는 문제를 정답이 가능한 값의 범위를 구하고 그 중간 값으로 정답이 가능한지 판단하면서 정답 가능 범위를 줄여나가면서 푸는 방법(이분탐색으로 풀 수 있게 바꾼다)을 parametric search라고 한다고 한다.

그냥 이분탐색 문제인 줄 알았는데 네이밍이 따로 있는건 지금 알았네.

 

그나저나 h-index 관련 문제를 이전에도 푼 것 같은데.. 문제번호를 못찾겠다.

사실 h가 너무 많이 나와서 몇 번을 읽어도 이해가 잘 안된다. 보자마자 이분탐색 문제네. 싶다가도 h-인덱스가 뭐지, 조건을 어떻게 걸어야 하지. 고민하는데 생각보다 시간이 오래 걸렸다. 당땡긴다..