[백준/BOJ] 백준 2002번 : 추월

2021. 3. 1. 03:47알고리즘 문제풀이

www.acmicpc.net/problem/2002

 

2002번: 추월

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이

www.acmicpc.net

들어갈 때 차의 순위를 map<string, int> in_t에 저장하고, 나오는 차를 순서대로 저장한 뒤 나올 때 순서가 빠른 차부터 더 늦은 차량들을 확인하며 추월을 했는지 판단한다.

 

코드

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

int n;
map<string, int> in_t;
vector<string> out_t;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		in_t.insert(make_pair(input, i)); //들어갈때 차의 순위 저장
	}

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		out_t.push_back(input); //나오는차 순서대로 저장
	}

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		int i_in_rank = in_t[out_t[i]]; //나올때 순위가 i인 차의 들어갈때 순위
		for (int j = i + 1; j < n; j++)
		{
			int j_in_rank = in_t[out_t[j]]; //나올때 순위가 j인 차의 들어갈때 순위

			if (i_in_rank > j_in_rank) //추월했을때 (나올때 순위 i인 차가 나올때 순위 j인 차를 추월한것일때)
			{
				result++;
				break;
			}
		}
	}

	cout << result;

	return 0;
}