BOJ 2002 : 추월

• 문제 링크 : boj.kr/2002
• 난이도 : S2
• 태그 : 맵, 셋

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    map<string, int> _m;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        _m[s] = i+1;
    }

    vector<int> arr;
    set<int> _s;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(auto e : arr) {
            if(e > _m[s]) {
                _s.insert(e);
            }
        }
        arr.emplace_back(_m[s]);
    }
    cout << _s.size();

    return 0;
}

---

풀이

차 k를 기준으로 어떤 차 a가 터널에 들어가기 전에는 뒤에 있었지만 터널에서 나올 때 앞에 있다면 차 a는 추월을 한 것이다.