[Softeer] Lv3.자동차 테스트

https://softeer.ai/practice/6247

처음에 문제를 보고 중간값에 해당하는 값보다 작은수 개수 * 큰 수의 개수 를 하면 답이 될꺼같았다.

그거를 어떻게 찾아낼까,,, 하다 이분탐색이 맨처음에 생각났다. 근데 한개의 수만 찾는게 아닌 최대 20만개의 수를 찾아야 했었다.
5,2,3,1,6 이면 (0,5),(1,2),(2,3),(3,1),(4,6) 로 묶여서 vector에 넣고 .second 로 오름,내림 sort를 하게 되면 각각의 값이 나오게 될것이다.
그럼 두개의 결과창에 각 값의 큰수와 작은수를 저장하면 될꺼같았는데,, 너무 복잡했다.
일단 안되면 이렇게 해야겠다 라고 생각하고

그렇게 생각을 계속하다보니,,, 그냥 정렬하고 자신의 인덱스 자체가 크고,작은수의 개수를 알려줄수있었다.

5,2,3,1,6 - >1,2,3,5,6 이 될꺼고 1보다 작은건 0개 큰건 4개,,,
그래서 그냥 이방식으로 풀기로함

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

using namespace std;

int N,Q;
vector<int> v;
unordered_map<int,pair<int,int>> m; // first 는 자기보다 작은수 , second 는 큰수

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N >> Q;
    for(int i=0;i<N;i++) {
        int data;
        cin >> data;
        v.push_back(data);
    }
    sort(v.begin(),v.end());
    
    for(int i=0;i<N;i++) {
        m[v[i]].first=i;
        m[v[i]].second=N-i-1;
    }
    
    for(int i=0;i<Q;i++) {
        int data;
        cin >> data;
        if(m[data].first==0 and m[data].second==0) {
            cout << 0 << "\n";
            continue;
        }
        cout << m[data].first*m[data].second << "\n";
    }
    
    return 0;
}

마지막 출력쪽에보면 .first , .second 가 둘다 0이면 없는수로 가정했다.
맨처음,맨마지막에 있는 수는 .first,.second가 각각 0이기 떄문에 없는수는 둘다 0인것.