추월

문제 링크

추월

아이디어

• 추월의 의미를 명시화하는 것이 중요

  • \(i\) 번째 차가 추월 차량이기 위해서는 \([0, i - 1]\) 까지의 차량들이 나가는 시점보다 더 빨라야한다.

• \(i\) 번째 차가 추월 차선인지 판단하는 로직

  • \([0, i - 1]\) 차량이 나가는 시점이 어느 지점인지 확인

  • for (int j = 0; j < i; j++) {
        string target = j번째 차량의 이름;
        int tgt_idx = -1;
    	for (int k = 0; k < N; k++) {
            if (exit[k] == target) {
                tgt_idx = k;
                break;
            }
        }
    }
    

• \(N\) 번째 차까지 모두 고려하기 위해서는 최적화가 필요

  • ${name} 이름의 차가 나가는 시점을 미리 전처리

  • map<string, int> mp;
    for (int i = 0; i < N; i++) {
    	string name = entry[i];
        for (int j = 0; j < N; j++) {
            if (exit[j] == name) {
                mp[name] = j;
            }
        }
    }
    

  • 전처리에 필요한 비용 \(O(N^2)\)

• ${name} 이름의 차량이 나가는 지점을 전처리 과정을 통해서 \(O(logN)\) 의 시간에 구할 수 있음

• 전처리를 통해서 문제를 \(O(N^2 logN)\) 의 시간에 해결할 수 있다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int N;
    cin >> N;

    vector<string> entry(N), exit(N);
    for (auto &elem : entry) cin >> elem;
    for (auto &elem : exit) cin >> elem;

    map<string, int> posAtEnd;
    for (int i = 0; i < N; i++) {
        const string& target = entry[i];
        for (int j = 0; j < N; j++) {
            if (exit[j] == target) {
                posAtEnd[target] = j;
                break;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        bool flag = false;
        for (int j = 0; j < i; j++) {
            if (posAtEnd[entry[j]] > posAtEnd[entry[i]]) {
                flag = true;
                break;
            }
        }
        if (flag) {
            ans++;
        }
    }

    cout << ans;
    return 0;
}