[백준] 2002번: 추월

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

2002번: 추월

쉬워보였지만, 역시나 나는 나약했다..

 

해시맵을 통해 차량 이름과 입장 순서를 매핑한다.

그리고 입장 순서보다 나가는 순서가 빠르면 추월한 것으로 처리했다.

하지만 통과할 수 없었다.

왜냐하면 만약 나가는 순서와 입장 순서가 동일해도 만약 해당 차보다 일찍 들어온 차가 뒤에 있으면 추월한 경우로 간주해야한다.

그래서 이렇게 한 번만 루프를 돌면서 파악하는 것은 어렵다고 판단한 후, 이중 루프로 다른 차량과의 비교를 한다.

그 때 비교하는 방식이 중요하다.

0, 1, 2, 3 순서로 들어온 경우라면 1, 2, 3, 0 순서로 들어왔을 때 반드시 추월하는 차량은 3대가 아니라 1대이다.

즉 이를 통해서 앞서가는 차보다 늦게 터널에 나오는 차를 세어야 한다.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<string, int> cars;
int main() {
	int n, answer = 0;
	string car;
	cin >> n;
	for(int i = 0;i < n;i++) {
		cin >> car;
		cars[car] = cars.size();
	}

	vector<int> tunnel(cars.size());
	// num번째 들어온 차량은 i번째에 나갔다
	for(int i = 0;i < n;i++) {
		cin >> car;
		int num = cars[car];
		tunnel[num] = i;
	}

	for(int i = 0;i < n;i++) {
		for(int j = 0;j < i;j++) {
			if(tunnel[i] < tunnel[j]) {
				answer++;
				break;
			}
		}
	}

	cout << answer<< '\n';
}