[백준] 2002. 추월

문제

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

풀이

뭔가 O(n^2) 에 대해 부정적인 의식이 있다보니 문제를 제대로 안 보고 '이걸 어떻게 한 번에 다 탐색하지?' 했는데 차량 수가 1000대 정도밖에 안되는 것을 보고 바로 O(n^2)으로 풀었다.

상식적인 선에서 해결하면 되는 문제인데, 각 차에 추월이 없을 때의 순서로 번호를 붙이고 (즉 들어갈 때의 순서로 번호를 붙이고), 터널을 나오는 차에 그 차에 들어갈 때 붙였던 번호를 똑같이 붙여서 저장해준다. 각각 before, after 벡터로 저장했다. 또한 추월했는지를 체크하기 위한 배열을 따로 만들었다. 이 배열을 go라고 하자.

이제 after 벡터를 돌면서 현재 탐색 중인 차보다 작은 인덱스를 전부 체크하면서 현재 차보다 붙인 번호가 큰 차가 존재한다면 go[번호] = 1로 체크해준다. 모든 차를 탐색한 후 go = 1인 것을 세서 출력해주면 된다.

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int main(){

    int ans = 0;
    int go[1001] = { 0, };
    vector<pair<string, int> > before, after;
    int N; cin >> N;
    for(int i = 0; i < N; i++){
        string s; cin >> s;
        // 터널을 들어가기 전 차에 번호를 붙인다.
        before.push_back(make_pair(s, i));
    }
    for(int i = N; i < N * 2; i++){
        string s; cin >> s;
        for(int j = 0; j < N; j++){
            // before에서 같은 차를 찾아서 번호를 확인한 후 after에 쌍으로 저장해준다. 
            if(before[j].first == s){
                after.push_back(make_pair(s, j));
                break;
            }
        }
    }
    // after를 처음부터 돌면서 현재 탐색 중인 차보다 앞에 있는 차 중에서 들어간 순서 번호가 더 큰 차가 있다면 추월한 차이므로 go[터널을 들어간 순서 번호] = 1로
    // 바꿔준다.
    for(int i = 1; i < N; i++){
        for(int j = 0; j < i; j++){
            if(after[i].second < after[j].second){
                go[after[j].second] = 1;
            }
        }
    }

    for(int i = 0; i < N; i++){
        if(go[i] == 1) ans++;
    }

    cout << ans;
    return 0;
}