[Softeer] 자동차 테스트 with C++ (HSAT 7회 기출)

https://softeer.ai/practice/6247

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

언어: C++, 시간: 406ms

이진탐색을 꼭 써야 시간초과가 안 나는문제! 

 

핵심 풀이 방법:

1. 오름차순으로 정렬을 우선 때린다

2. 쿼리에서 주어진 mi에 따라 중앙값이 나오는 가짓수를 판단한다:

-> 주어진 n개의 수 중 가장 작거나 가장 큰 값이었을때: 절대 중앙값이 될 수 없다, 0

-> 중간에 있는 값이었을때: 경우의 수는 mi 보다 작은 숫자 개수 x mi보다 큰 숫자 개수

-> mi가 n개의 수 중 아무것도 아닐때: 0

 

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



int N, Q;
int startNum, endNum;
vector <int> vhicle;

int bs(int target){
    int startNum = 0;
    int endNum = vhicle.size()-1;
    int mid; 

    while (startNum <= endNum){
        mid = (startNum + endNum) / 2;
        if (vhicle[mid] == target)
            return mid;
        else if (vhicle[mid] < target)
            startNum = mid + 1;
        else
            endNum = mid -1;
    }
    return -1;
}


int main(int argc, char** argv)
{
    // 입력
    cin >> N >> Q;
    int temp;
    for(int i=0; i<N; i++){
        cin >> temp;
        vhicle.push_back(temp);
    }
    sort(vhicle.begin(), vhicle.end());

    startNum = vhicle[0];
    endNum = vhicle[vhicle.size()-1];

    // 쿼리
    int curQurry;
    for(int i=0; i<Q; i++){
        cin >> curQurry;

        if (curQurry <= startNum || curQurry >= endNum){
            cout << 0 << "\n";
        }
        else{
            int idx = bs(curQurry);
            int result;
            if (idx == -1)
                result = 0;
            else
                result = (idx) * (vhicle.size()-idx-1);
            cout << result << "\n";
        }
    }

    
    return 0;
}