백준 2002 - 추월

문제 설명

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 터널에 들어간 순서와 터널에서 나온 순서가 주어질 때 몇 대의 차가 추월했는지 계산하면 된다.

 

들어온 순서와 나온 순서를 매칭하면 문제를 간단하게 풀 수 있다.

나온 순서를 차례대로 살펴보다 자신보다 먼저 들어온 차가 있다면 해당 차량은 추월한 차이다.

예를 들어 들어온 순서대로 차를 0, 1, 2, 3, 4라고 했을 때 나온 순서가 {1, 4, 3, 0, 2}라면 1번 차량은 0번 차량보다 빠르게 터널을 빠져나왔으므로 추월한 차량이다.

마찬가지로 4번 차량도 3번 차량보다 빨리 나왔고 3번도 0번 차량보다 빨리 나왔다.

0번과 2번은 순서를 지켰으므로 해당되지 않는다. 

 

우선 들어온 순서와 나온 순서를 매칭하려면 직접 인덱스를 찾아도 되지만 map을 통해 이름 - 인덱스를 기록해 놓으면 이름으로 들어온 순서를 쉽게 조회할 수 있다.

for (int i = 0; i < N; i++)
{
    string name;
    cin >> name;
    in[name] = i;
}

for (int i = 0; i < N; i++)
{
    string name;
    cin >> name;
    out[i] = in[name];
}

 

이제 나온 차량을 하나씩 살펴보며 자신 뒤에 더 작은 숫자가 있는지 살펴보면 된다.

for (int i = 0; i < N - 1; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        if (out[i] > out[j])
        {
            ans++;
            break;
        }
    }
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
map<string, int> in;
vector<int> out;

int main()
{
	INPUT_OPTIMIZE;

	cin >> N;
	int ans = 0;
	out.resize(N);

	for (int i = 0; i < N; i++)
	{
		string name;
		cin >> name;
		in[name] = i;
	}

	for (int i = 0; i < N; i++)
	{
		string name;
		cin >> name;
		out[i] = in[name];
	}

	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			if (out[i] > out[j])
			{
				ans++;
				break;
			}
		}
	}

	cout << ans;

	return 0;
}

---