백준 7795 먹을 것인가 먹힐 것인가 c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 시간초과 오류가 났다.

#include <iostream>
using namespace std;

int main(){
    int t;
    cin >> t;
    
    for(int i=0; i<t; i++){
        int n, m;
        cin >> n >> m;
        
        int arr1[n];
        int arr2[m];
        for(int j=0; j<n; j++)
            cin >> arr1[j];
        for(int k=0; k<m; k++)
            cin >> arr2[k];      
        
        int count = 0;
        for(int j=0; j<n; j++){
            for(int k=0; k<m; k++){
                if(arr1[j] > arr2[k])
                    count++;
            }
        }
        
        cout << count << "\n";
    }
    
    return 0;
}

 

 

 

다시 작성한 코드는 다음과 같다.

시간 문제를 해결하기 위해 sort함수로 미리 정렬을 해놓은 후, 탐색할 때 이중 for문을 다 돌게 하는 것이 아니라 적당히 돌다가 break를 통해 끊어가도록 한다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int t;
    cin >> t;
    
    for(int i=0; i<t; i++){
        int n, m;
        cin >> n >> m;
        
        int arr1[n];
        int arr2[m];
        for(int j=0; j<n; j++)
            cin >> arr1[j];
        for(int k=0; k<m; k++)
            cin >> arr2[k];      
        
        sort(arr1, arr1+n);
        sort(arr2, arr2+m);
        
        int count = 0;        
        for(int j=0; j<n; j++){
            for(int k=0; k<m; k++){
                if(arr1[j] > arr2[k])
                    count++;
                else 
                    break;
            }
        }
        
        cout << count << "\n";
    }
    
    return 0;
}