[백준] 2002. 추월 (C++)

Level

silver1

 

 

Idea

추월을 하게 되면 내 뒤에 나보다 작은 수(입력 순서가 나보다 빨랐던 차)가 하나라도 존재하게 된다. 이 점을 이용해서 문제를 풀었다. 입력 순서는 map을 활용하여 저장했다.

 

Key Point

 추월을 했다 != 맨 앞으로 나갔다 라는걸 명심해야한다!! 나는 아무 생각없이 '추월했으면 맨 앞에 위치하겠지' 라고 생각하고 문제를 풀어서 계속 헤맸다. 그러니까 1 2 3 4 5 에서 4 5 가 추월했다고 4 5 1 2 3 이런식으로 되는게 아니란 소리다. 그냥 내 앞에 있던 차보다 앞으로 가면 추월이다. 당연한 소리인데 나는 왜 그랬을까? 어쩐지 실버 1문제가 너무 빨리 풀린다했다..

 아무튼 이렇게 잘못 접근해서 처음 짠 코드는 아래와 같다. mp와 mp2에 각각 차 이름과 등수를 넣는다. 그리고 mp[자동차이름]과 mp2[자동차이름] 을 비교해서 등수를 비교했다. 이렇게 풀면 맨 앞이 아니고 중간에 끼어든 차는 카운팅하지 못할 수도 있다. 예를 들어보자. 1 2 3 4 순서로 터널에 들어갔는데 3이 2를 추월하고 4가 맨 앞으로 추월하면 4 1 3 2가 된다. 이 때 3은 추월을 했음에도 들어갈 때와 같은 자리에 위치해있다.

 그러므로 들어간 순서는 신경쓰지 말고 나온 순서에서 추월한 개수를 파악해야한다. 원래는 오름차순으로 정렬되어있으니까 내 앞엔 나보다 작은 수 밖에 없고 내 뒤엔 나보다 큰 수밖에 없다. 그러나 추월을 하게 되면 내 뒤에 나보다 작은 수가 올 수 있다. 이 포인트를 이용해서 문제를 해결해야한다.

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

int main() {

	int n = 0;
	string st;
	int cnt = 0;

	map<string, int>mp;
	map<string, int>mp2;
	vector<string>v;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> st;
		mp.insert({ st,i });
		v.push_back(st);
	}

	st = "";

	for (int j = 0; j < n; j++) {
		cin >> st;
		mp2.insert({ st,j });
	}

	for (auto a : v) {
		
			if (mp[a] > mp2[a]) cnt++;
			
	}


	cout << cnt << endl;

	return 0;
}

 

 

Code

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

int main() {

	int n = 0;
	int cnt = 0;
	string st;
	map<string, int>mp;

	int arr[1001];

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> st;
		mp.insert({ st,i });
	} // 터널에 들어간 순서를 mp에 저장

	st = "";

	for (int j = 0; j < n; j++) {
		cin >> st;
		int order = mp[st];
		arr[j] = order;
	} // mp를 이용해서 터널에서 나온 순서를 arr에 저장

	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (arr[i] > arr[j]) {
				cnt++;
				break;
			}
		}
	}

	cout << cnt << endl;

	return 0;
}