[C++] 백준 2002 - 추월

백준 2002-추월

문제

소스코드1

#include<iostream>
#include<map>

using namespace std;

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

	int n;
	int min = 10000; // 더 빨리 들어간 순서를 알기 위한 변수
	string input; 
	int out[1000]; //나온 차 순서대로 들어간 순서가 저장됨
	int count = 0;
	map<int, string> car;
	map<int, string>::iterator iter;

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> input;
		car[i] = input;
	}

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

		for (iter = car.begin(); iter != car.end(); iter++) {
			if (iter->second == input) { 
				out[i] = iter->first;  //들어간 순서 저장
				break;
			}
		}
	}

	for (int i = n; i > 0; i--) { //추월한 차 대수 세기
		if (out[i] < min) {
			min = out[i];
		}

		if (out[i] > min) {
			count++;
		}

	}
	cout << count;
	
}

해설1

처음 생각한 방식은 map의 key 값에 순서, value 값에 차번호를 넣어주는 것이었다.
그래서 out배열에 들어간 순서를 저장할때 input과 일치하는 value값을 찾아야해서 for문을 한번 더 사용하였다.

추월한 차를 세는 방법을 설명해 보자면,
일단 가장 마지막으로 나간 차부터 시작한다.
더 먼저 진입한 차가 나오면 그 차를 min이라는 변수에 넣는다.
min을 기준으로 먼저 나간차가 더 늦게 진입한 차인가를 세는 방식으로 했다. (설명을 잘 못해서 죄송합니다ㅠㅠ)

이렇게 코드를 작성해서 맞긴했지만 out배열을 저장하는 부분에서 이중for문을 사용하는 것이 마음에 안들어 다시 생각해봤다.

처음 생각할 때는 map의 key 값에 순서, value 값에 차번호를 넣어야한다는 생각이 강했는데 다시 생각해보니 반대로 저장하는게 더 깔끔하겠다는 생각이 들었다.

소스코드2

#include<iostream>
#include<map>

using namespace std;

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

	int n;
	int min = 10000;
	string input;
	int out[1000];
	int count = 0;
	map<string, int> car;
	map<int, string>::iterator iter;

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> input;
		car[input] = i;
	}

	for (int i = 1; i <= n; i++) { //바뀐 부분
		cin >> input;

		out[i] = car[input];
	}

	for (int i = n; i > 0; i--) {
		if (out[i] < min) {
			min = out[i];
		}

		if (out[i] > min) {
			count++;
		}

	}
	cout << count;
	
}

해설2

두번째 방식은 map의 key값에 차번호, value값에 순서를 넣어주는 것이다.
이 방식에서는 out 배열을 저장할 때 key값으로 value를 바로 찾을 수 있어 이중 for문을 사용하지 않을 수 있었다.
나머지 방식은 동일하다.