[BOJ 2002 // C++] 추월

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2002번 문제인 추월이다.
문제는 아래 링크를 확인하자.

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

2002번: 추월

모든 차의 차량 번호는 다르므로 각 차들을 터널에 들어간 순서대로 0, 1, 2... 과 같이 번호를 붙여 생각할 수 있다.

 

이 때, 번호 i를 가진 차가 j<i인 번호 j를 가진 어떤 차보다 터널에서 먼저 나온다면 번호 i를 가진 차는 적어도 번호 j를 가진 차를 앞질렀음을 알 수 있다.

 

N의 범위가 작으므로, 각 번호 i에 대하여 위의 조건을 만족하는 j가 존재하는지를 일일이 반복문을 이용해 찾는 \(O(N^2)\) 알고리즘을 통해 문제를 해결할 수 있다.

 

아래의 코드는 "터널에서 아직 나오지 않은 가장 작은 차량 번호"를 관리해 효율적(\(O(N)\))으로 문제를 해결한 것이다. 각 차량이 터널에서 나올 때, 해당 차량의 번호가 위의 값보다 크다면 못해도 그 값을 갖는 차량을 추월했을 수밖에 없고, 그렇지 않다면 해당 차량이 그 번호를 갖는 차가 될 수밖에 없음을 관찰해보자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int N;
map<string, int> mp;
int visited[1001], idx, cnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		string s; cin >> s;
		mp.insert(make_pair(s, i));
	}

	while (N--) {
		string s; cin >> s;
		int i = mp[s];
		if (idx < i) cnt++;
		visited[i] = 1;
		while (visited[idx]) idx++;
	}

	cout << cnt;
}