https://www.acmicpc.net/problem/2002
문제
> 대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다.
> 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다.
> 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.
> 소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다.
> 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고,
대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.
> N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고,
터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다.
> 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.접근
터널에 들어온 차들의 번호를 Key값으로 string,int형 map에 value값으로 터널에 들어온 순서를 저장한다.
터널에서 나올 땐 터널에 나온 순서대로 벡터에 차의 번호에 맞는 value값인 들어왔던 순서를 저장한다.
그럼 예를 들면 out(0) = 3이면 나올땐 제일먼저 나갔지만 들어올 땐 3번째로 들어왔던 차 라는 뜻이다.
순서 정리가 끝나면 차들의 순서를 비교한다.
나온 순서인 out벡터를 순서대로 뒤에 온 차들과 비교한다.
처음 들어올 때, 1부터 n까지 차례대로 들어왔으므로 추월을 하지 않았다면 각 차들은 본인의 순서보다 작은 순서 였던 차량이 자신의 뒤에 있으면 안된다.
따라서 out끼리 비교했을 때 만약 내 뒷번 순서 차량이 나보다 들어오왔던 순서가 먼저인(더 작은값) 순서를 가지면 추월했다는 뜻이된다. 이를 누적한다.
문제해결
> 들어온 순서를 기록할 string, int형 맵과 나갈 순서를 저장할 벡터 out을 만든다.
> 차량의 수를 입력받고 i를 들어온 순서인 value값으로 차의 번호를 key로 map에 저장한다.
> out벡터에 나온 순서대로 차량의 번호에 맞는 들어온 순서를 저장한다.
> 나온 차량을 순서대로 각각 뒷차량들이랑 비교해 만약 뒷 차량의 벡터값(들어왔던 순서)이 더 작다면 추월한 것이므로 cnt를 누적한다.
> 최종 추월차량의 수를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
map<string, int> inCar;
vector<int> out;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
inCar[str] = i;
}
int cnt = 0;
out.resize(N);
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
out[i] = inCar[str];
}
for (int i = 0; i < N - 1; i++)
{
for (int j = i + 1; j < N; j++)
{
if (out[i] > out[j])
{
cnt++;
break;
}
}
}
cout << cnt << '\n';
}
후기
처음에 그냥 나간 순서를 입력받을 때, i에 대해서 들어온 차량의 value가 다르다면, 즉 i는 0인데 inCar(str)이 3과 같이 순서가 바뀐 차가 있는데 만약 잉 i가 value보다 작으면 원래 순서보다 빨리 나갔다는 뜻이라 추월했구나로 생각해서 했는데 틀렸다.
왜 그런지 생각해보니 등 수는 똑같은데 추월은 한 차량을 놓치는 경우가 있었다.
예를 들어 1,2,3 차량이 있는데 나올 땐 3,2,1이라고 하자.
그럼 2차량은 내 처음 방식대로 하면 순서가 안바뀌었으므로 추월을 안한게 된다. 하지만 실제론 2는 1을 추월했지만 3에게 추월당해 그렇게 보인것이다.
