[BOJ][C++] 백준 2002번: 추월

문제

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

풀이

🔍 접근

1. 차가 들어간 순서를 숫자로 나타내기
2. A차가 다른 차를 추월했다는 것을 아는 방법
   (1) A의 들어갈 때 인덱스보다 나올 때 인덱스가 작으면 추월?
          → 들어갈 때 인덱스가 A보다 큰 차들이 추월하면서, A의 나올 때 인덱스도 뒤로 밀릴 수 있으므로
               A의 인덱스 비교만으로는 판단할 수 없다.
   (2) A보다 늦게 나온 차 중에서, A보다 들어갈 때 인덱스가 작은 차가 하나라도 있으면
         A보다 먼저 들어왔는데 A보다 뒤에 나온 것이므로 A는 터널 안에서 추월을 했다고 판단한다.

🔨 구현

1. map을 이용해 차량 번호(key)와 들어간 순서(value)를 저장한다.
2. vector에 나온 차의 차량 번호를 저장한다.
3. 나온 차를 순서대로 탐색하면서 map을 이용해 들어갈 때 인덱스를 비교한다.
   : 뒤에 나온 차들과 비교하면서, 들어갈 때 인덱스가 작은 차가 하나라도 있으면 정답(추월한 차) 증가.
     다음 차 탐색 진행.

코드

#include <iostream>
#include <map>
#include <vector>

using namespace std;

int passCar(int n, map<string, int> &enter, vector<string> &exit) {
    int ans = 0;

    for (int i = 0; i < n; i++) {   // 나온 차 탐색
        for (int j = i + 1; j < n; j++) {   // 뒤에 나온 차들과 비교
            // 들어갈 때 인덱스가 작은 차가 하나라도 있으면
            if (enter[exit[i]] > enter[exit[j]]) {
                ans++;
                break;
            }
        }
    }

    return ans;
}

int main() {
    int n, ans = 0;  // n: 차의 대수
    string input;
    map<string, int> enter;   // 대근(입구)
    vector<string> exit;    // 영식(출구)

    // 입력
    cin >> n;
    for (int i = 0; i < n; i++) {   // 들어간 차
        cin >> input;
        enter[input] = i;
    }
    for (int i = 0; i < n; i++) {   // 나간 차
        cin >> input;
        exit.push_back(input);
    }

    // 출력
    cout << passCar(n, enter, exit);

    return 0;
}