[백준,c++] 2002번 - 추월

문제

2002번: 추월

 

코드

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


using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    unordered_map<string, int> um;
    vector<string> inp;
    
    for(int i=0; i<N; i++){
        string _inp; cin>>_inp;
        um.insert({_inp, i});
    }
    
    
    for(int i=0; i<N; i++){
        string _inp; cin>>_inp;
        inp.push_back(_inp);
    }
   
    int cnt = 0;
    
    for(int i=0; i<inp.size(); i++){
        for(int k=i+1; k<inp.size(); k++){
            if(um[inp[i]] > um[inp[k]]){
                cnt++;
                break;
            }
        }
    }
    cout<<cnt;
}

 

풀이

단순하게 생각해야 하는 문제입니다.

5
1 2 3 4 5
2 3 1 5 4

위와 같은 입력이 주어졌다고 생각하고 정리해 보겠습니다.

먼저 터널 진입 차량마다의 순서를 다음과 같이 기록합니다.

[1] = 1, [2] = 2, [3] = 3, [4] = 4, [5] = 5

그 후, 터널을 나오는 차량을 살펴보는데, 자신의 차량 이후로 나오는 차량 중에서 자기보다 빨리 진입했던 차량이 있으면 추월을 한 것이 됩니다.

• 2를 기준으로 보았을때 [2] = 2, [1] = 1 이므로 2번 차량은 추월한 것이 됩니다.
• 3을 기준으로 보았을 때 [3]  = 3, [1] = 1이므로 3번 차량은 추월한 것이 됩니다.
• 1을 기준으로 보았을 때 [1] = 1 보다 작은 차량이 본인 이후로 없으므로 추월하지 않은 것이 됩니다.
• 5를 기준으로 보았을 때 [5] = 5, [4] = 4이므로 5번 차량은 추월한 것이 됩니다.
• 4를 기준으로 보았을 때 [4] = 4보다 작은 차량이 본인 이후로 없으므로 추월하지 않은 것이 됩니다.

unordered_map을 사용한 이유는 hash로 구현되어있기 때문이며 find시 O(1)의 시간 복잡도를 제공하기 때문입니다. 

map 같은 경우는 레드 블랙트리로 구현되어 있어서, O(logN)의 시간 복잡도를 제공합니다.