[BOJ/JAVA] 7795

👉🏼 문제

범위가 작아서 브루트포스로 풀었으나 다양한 풀이가 나올 것 같아서 기록해보고 한다!

첫번째 방법

사실 너무 쉬운 방법이다. a,b 정렬 후에 반복문 돌면서 a가 큰 개수 세기

Arrays.sort(b);

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (a[i] > b[j]) {
            cnt++;
        }
    }
}

대신 이 방법은 StringBuilder 써야한다! 안쓰면 시간초과임.

두번째 방법

(내림차순 정렬 후에) a가 b보다 큰 값이라면 그 뒤는 비교 안해도 전부 a가 더 큰 거 아닌가?

Arrays.sort(b, Collections.reverseOrder());

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (a[i] > b[j]) {
            cnt += m - j;
            break;
        }
    }
}

이분탐색

원래 목적인 이분탐색!

Arrays.sort(b);
for(int i = 0; i < n; i++) {
    int left = 0;
    int right = m-1;
    int cnt = 0;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[i] > b[mid]) {
            left = mid + 1;
            cnt = mid + 1;
        }
        else right = mid - 1;
    }
    result += cnt;
}