Lv. 3 자동차 테스트

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

using namespace std;

int binarySearch(vector<int>& arr, int n, int m) {
    int lo = 0;
    int hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == m)
            return mid;
        else if (arr[mid] < m) {
            lo = mid + 1;
        }
        else if (arr[mid] > m) {
            hi = mid - 1;
        }
    }
    return -1;
}

int main(int argc, char** argv)
{
    int n, q;
    cin >> n >> q;

    vector<int> arr(n);
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

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

    for (int i = 0; i < q; i++) {
        int m;
        cin >> m;

        if (m == arr[0] || m == arr[n - 1])
            cout << "0" << endl;
        else {
            // auto f = find(arr.begin(), arr.end(), m);
            int l = binarySearch(arr, n, m);
            if (l != -1) {
                cout << l * (n - l - 1) << endl;
            }
            else {
                cout << "0" << endl;
            }
        }
    }
    
    return 0;
}

정렬 때리고, m 값이 정렬된 배열의 처음이나 마지막 값이면, 0 출력
그렇지 않다면, m의 위치 정보를 찾아야하는데, find는 O(n)이기때문에 느리기에 이진탐색 사용해서 찾고, 있으면, 위치 * (n - 위치 - 1) 반환, 없으면 0