수열과 쿼리 1 문제와 거의 같은 문제이다. 그 때 시간을 줄여도 시간이 2000ms 넘게 걸려서 고민이 됐는데, k보다 큰 수의 개수를 찾는 과정에서 이분 탐색의 Upper Bound 알고리즘을 쓰면 시간을 줄일 수 있다.
원래는 이렇게 풀었다.
static int findBigger(int[] arr, int k) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] > k) return arr.length - i;
}
return 0;
}Upper Bound 알고리즘을 쓰면 다음과 같다.
static int upper_bound(int node, int k) {
int left = 0, right = mst[node].length -1, mid;
while (left < right) {
mid = (left + right) / 2;
if (mst[node][mid] > k) right = mid;
else left = mid + 1;
}
if (mst[node][right] > k) return right;
else return mst[node].length; // mst[node] 배열의 길이가 0인 경우 처리
}
실행 시간이 거의 반 이상 줄어드는 것을 확인할 수 있다.