[Softeer] 자동차 테스트 (C++)

📝 제출코드 #1 (시간 초과)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int q, m;
    int r=0; // result counting variable
    vector<int> car;
    vector<int> mid;

    // for starting from index 1
    car.push_back(0);
    
    scanf("%d %d", &q, &m);
    // 자동차 연비 넣기
    for(int i=1; i<=q; i++){
        int n;
        scanf("%d", &n);
        car.push_back(n);
    }

    sort(car.begin(), car.end());

    // 중앙값 넣기
    for(int i=1; i<=m; i++){
        int num; 
        scanf("%d", &num);
        mid.push_back(num);
    }

    for(int i=0; i<m; i++){ 
        auto it = find(car.begin(), car.end(), mid[i]);
        // if m_i not in car, print result and continue
        if( it == car.end()) {
            printf("0\n");
            continue;
        } 
        
        int pos = distance(car.begin(), it);
        
        for(int i=1; i<pos; i++){
            for(int j=pos+1; j<=q; j++) r++;
        }
        printf("%d\n", r);
        r=0;
    }
    return 0;
}

생각나는 풀이로 구현한 코드로, 반복문이 3개가 중첩되어서 복잡도가 높아 TC셋 하나만 통과하고 나머지 두개는 시간초과가 났다.

 

📝 제출코드 #2 (시간 초과)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int q, m;
    int r=0; // result counting variable
    vector<int> car;
    vector<int> mid;

    // for starting from index 1
    car.push_back(0);
    
    scanf("%d %d", &q, &m);
    // 자동차 연비 넣기
    for(int i=1; i<=q; i++){
        int n;
        scanf("%d", &n);
        car.push_back(n);
    }

    sort(car.begin(), car.end());

    for(int i=0; i<m; i++){
        int mid;
        scanf("%d", &mid);
        
        auto it = find(car.begin(), car.end(), mid);
        
        // if m_i not in car, print result and continue
        if( it == car.end()) {
            printf("0\n");
            continue;
        } 
        // find index of mid
        int pos = distance(car.begin(), it);

        if(pos == 1) {
            printf("0\n");
            continue;
        }

        // 가짓수는 mid보다 작은 개수*mid보다 큰 개수
        printf("%d\n", (pos-1)*(q-pos));
    }
    return 0;
}

TC셋 3개 중 한 세트에서 하나의 테스트케이스가 시간초과가 발생했다..........

 

📝 제출코드 #3 (통과)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
    int q, m;
    vector<int> car;
    vector<int> mid;

    // for starting from index 1
    car.push_back(0);
    
    scanf("%d %d", &q, &m);
    // 자동차 연비 넣기
    for(int i=1; i<=q; i++){
        int n;
        scanf("%d", &n);
        car.push_back(n);
    }

    sort(car.begin(), car.end());

    for(int i=0; i<m; i++){
        int mid;
        scanf("%d", &mid);
        
        auto it = find(car.begin(), car.end(), mid);
        
        // if m_i not in car, print result and continue
        if( it == car.end()) {
            printf("0\n");
            continue;
        } 
        // find index of mid
        int pos = distance(car.begin(), it);

        // 가짓수는 mid보다 작은 개수*mid보다 큰 개수
        printf("%d\n", (pos-1)*(q-pos));
    }
    return 0;
}

pos가 첫 번째인 경우에도 출력 시 pos-1으로 0이 되므로 따로 고려 안 하는 것으로 수정했다.