백준 2002 - 추월(C++)

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

2002번: 추월

 

풀이

map 사용하는 문제에 재미 들렸다 ㅎ

먼저 map에 입력되는 차량 번호와 순서(0~n의 값을 갖는 각 차량의 번호표)를 저장한다.

추월하지 않았다면 들어와야 했을 번호를 idx에 저장한다.

배열을 생성해서 차가 터널에서 나가면 앞서 저장한 번호표에 해당하는 인덱스로 가서 1을 입력한다.

(3번 번호표를 갖는 차가 나가면 arr[3]의 값을 1로 변경. 이 과정이 없으면 이미 나간 3번 차례를 계속 기다리게 될 수 있다.)

idx부터 시작해서 배열의 값이 1인 동안 idx를 계속 증가시킨다. (배열의 값이 1이면 이미 빠져나간 차이므로) 

현재 나가는 차가 idx와 다르다면 추월을 한 차일 것이므로 cnt를 증가한다.

코드

#include <iostream>
#include <map>
#include <string>
using namespace std;
int arr[1001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    map<string,int> m;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        m.insert({s,i});
    }
    int idx=0, cnt=0;
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        while(arr[idx]!=0 && idx<n) idx++;
        arr[m[s]]=1;
        if(m[s]!=idx) cnt++;
        else idx++;
    }
    cout<<cnt;
}