[BOJ 7795] 먹을 것인가 먹힐 것인가

수열 A와 수열 B가 주어졌을 때, 수열 A의 원소들이 수열 B의 원소들보다 큰 쌍이 몇 개나 있는지 구하는 문제이다. 2가지 방법으로 해결할 수 있다. 

 

1. A, B 모두 정렬 후, 투 포인터 

2. B만 정렬 후, 이분 탐색 

 

2번의 경우 lower_bound을 이용해서 바로 풀어주면 된다.

 

1번의 경우는 merge sort에서 쪼개었던 두 배열을 다시 합칠 때 정렬하는 형태를 이용하자. A, B 모두가 정렬되어 있다면 A의 앞에서 나온 원소보다 뒤에 나온 원소가 B의 더 뒤의 원소들보다 클 것이다. 이를 이용해서 해결해주면 된다.

 

int main(void) {
    fastio;
    cin >> T;
    while (T--) {
        cin >> N >> M;
        for (int i = 0; i < N; i++)
            cin >> A[i];
        for (int i = 0; i < M; i++)
            cin >> B[i];
        sort(B, B + M);

        int cnt = 0;
        for (int i = 0; i < N; i++)
            cnt += lower_bound(B, B + M, A[i]) - B;
        cout << cnt << "\n";
    }
    return 0;
}

 

풀이는 2번의 풀이만 공유한다.