백준 / 실버 2 / 2002 추월 / C++ [맵]

https://www.acmicpc.net/problem/2002

처음 풀이

/******************************************************************************


0 1 2 3 4

4 0 1 3 2

오른쪽에 더 작은 수가 있으면 n은 추월한 것


*******************************************************************************/

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, i, j, a=0;
    cin >> n;
    
    unordered_map<string, int> in;
    vector<int> v(n);
    
    for(i=0; i<n; i++){
        string s;
        cin >> s;
        in[s] = i;
    }
    for(i=0; i<n; i++){
        string s;
        cin >> s;
        v[i] = in[s];
    }
    for(i=0; i<n; i++){
        for(j=i+1; j<n; j++){
            if(v[i] > v[j]){
                a++;
                break;
            }
        }
    }
    cout << a;
}

캐시 적용해 개선

/******************************************************************************

0 1 2 3 4

4 0 1 3 2

원래 더 앞이었던 차가 하나라도 덜 나왔으면 추월한 것
for j < i
    if 안나옴(i)
        a++


*******************************************************************************/
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, i, j, a = 0;

    cin >> n;
    unordered_map<string, int> order(n);
    bool out[1001] = {false,};
    string car;
    
    for(i=0; i<n; i++){
        cin >> car;
        order[car] = i;
    }
    for(i=0; i<n; i++){
        cin >> car;
        out[order[car]] = true;
        for (int j=0; j<order[car]; j++) {
            if (!out[j]) {
                a++;
                break;
            }
        }
    }
    cout << a;
}

bool cache[1001] = {false,};