[백준 7795번] 먹을 것인가 먹힐 것인가 (C++)

문제링크 : https://www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, A, B;
int arr1[20001], arr2[20001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    while(T--)
    {
        cin >> A >> B;
        for(int i=0; i<A; i++) cin >> arr1[i];
        for(int i=0; i<B; i++) cin >> arr2[i];

        sort(arr1, arr1+A);
        sort(arr2, arr2+B);

        int result = 0;
        for(int i=0; i<A; i++)
        {
            for(int j=0; j<B; j++)
            {
                if(arr1[i] > arr2[j]) result++; //크면 카운팅
                else break; //이후는 의미없으므로 종료
            }
        }
        cout << result << "\n";
    }

    return 0;
}

 

테스트 케이스를 고려안하고, 최대 범위가 2만 * 2만이라 괜찮을 줄 알고 브루트포스로 풀었더니 시간초과가 발생했다.

 

이에 입력받은 각 배열을 정렬하고, arr1이 arr2보다 크면 카운팅해주고 아닌 경우 이후로는 쭉 의미가 없으므로 바로 종료시켜줌으로써 시간초과를 벗어날 수 있었다.