백준 19637 IF문 좀 대신 써줘 c++

 

 

 

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

하지만 시간초과라는 결과가 떴다.

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

int main(){
    int n,m;
    cin >> n >> m;
    
    string str[n];
    int num[n];
    for(int i=0; i<n; i++){
        cin >> str[i] >> num[i];  
    }
    
    int temp;
    for(int i=0; i<m; i++){
        cin >> temp;
        for(int j=0; j<n; j++){
            if(temp <= num[j]){
                cout << str[j] << "\n";
                break;
            }
        }
    }
    
    return 0;
}

 

 

 

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

순서대로 하는 탐색은 시간복잡도가 n^2가 나오니 이분탐색을 사용해 시간복잡도를 줄였다.

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

string str[100000];
int num[100000];
int n,m;

int binsearch(int p){
    int mid = 0, left = 0, right = n-1;
    while(left <= right){
        mid = (left+right)/2;
        if(p <= num[mid])
            right = mid-1;
        else
            left = mid+1;
    }
    if(p > num[mid])
        return mid+1;
    else
        return mid;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        cin >> str[i] >> num[i];  
    }
    
    int temp;
    for(int i=0; i<m; i++){
        cin >> temp;
        cout << str[binsearch(temp)] << "\n";
    }
    
    return 0;
}