백준 / 2002 추월 C++

www.acmicpc.net/problem/2002

2002번: 추월

터널 내의 차선 변경이 불가능할 때 추월 차량이 얼마나 되는지 묻는 문제입니다.

(하지만 실제로는 큰 터널의 경우 추월가능한 터널도 있다.)

 

처음에는 dp로 생각하여 들어갈 때 내 차량 앞에 몇 대의 차량이 있는지를 계산하여 풀려했지만, 예제 몇 개를 떠올려보니 2번이 1번을 추월하고 1번이 2번을 다시 추월하고 그러면 계산이 꼬이는 경우가 있어서 다른 방법으로 풀었습니다.

 

C++에서 map 컨테이너를 이용해 들어갈 때 순서를 기록하고, 나올 때 순서를 value 값을 output 배열에 넣습니다. 그리하여 output[i]를 output[i+1]~output[n-1]까지와 비교하여 하나라도 큰 값이 존재하면 (output[i] > output[j]) 추월한 경우입니다.

 

사실 map 컨테이너를 안 쓰고 그냥 배열이나 리스트를 이용해서 들어갈 때 순서를 기록해 탐색해도 되지만 (n<=1000, 그냥 순차 탐색해도 O(n)) 한 번 써봤습니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>

using namespace std;

int n;
map<string, int>m; // {차량 번호 : 들어간 순서}
int* output;

void init()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		m[s] = i;
	}

	output = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int idx = m[s];
		output[i] = idx;
	}
}

// 추월 계산
// map의 value(들어간 순서) 와 비교하여 
// i번째 차의 나온 순서(output)를 
// i+1 번째~n-1번째 차의 나온 순서와 비교 (i>=0)
// 더 큰 경우 하나라도 있으면 i번째 차는 추월한 것

int overtake()
{
	int result = 0;

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

	return result;
}

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

	init();
	cout << overtake();
}