2002.超える

質問リンク

1.トラブルシューティング

コア記事では、同じ車両番号を2回以上与えていない.はい.
追い越しとは、トンネルに入ると遅れて来た車が出るのが速いという意味です.この部分に焦点を当てて問題を解決すべきだ.
従って、実施手順は以下の通りである.

1. 입력으로 주어지는 2~N개의 차량번호를 Map<String,Integer>에 저장한다.
2. N+2 ~ N개의 차량 번호를 Key값으로 하여 Map에 저장된 값을 배열에 할당한다.
3. 2번에서 구한 배열을 뒤에서 부터 순회하면서 현재 차량 순서와 이전 차량 순서를 비교해 가며 차량의 최소 번호를 배열에 할당한다.
 3-1. 이전 차량 순서 < 현재 차량 순서일 경우, 추월했다는 의미이다.

1-1. オペレーションプロセス

例入力1は、以下に示すように、上記の手順で行います.次の動作過程は1、2回の過程を経た後の様子です.
SEQは、当該車両番号の進入順を示す

1.ナンバープレートST 123 DとZG 5080 Kの進入順を比較する.
ナンバーZG 5080 KはST 123 Dより進んでいるので、超えていません.

2.ナンバープレートZG 431 SNをZG 5080 Kと比較する.1番と同じように超えていません.

3.ナンバープレートZG 206 AとZG 431 SNを比較する.
ZG 431 SNは入場時に0番に入ったが、ZG 206 Aは3番目に入った.これはZG 206 AがZG 431 SNを超えたことを意味する.

4.第3のプロセスの後、前の車両はナンバープレートZG 431 SNより駅に入るのが遅く、説明が先に出た.
これを表現するために、SEQを車号ZG 431 SNのSEQに変更した.

2.ソースコード

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		String [] input = new String[n];
		
		for(int i =0 ; i < n ; i++) {
			input [i] = br.readLine();
		}
		
		String [] output = new String[n];
	
		for(int i =0 ; i < n ; i++) {
			output[i] = br.readLine();
		}
		
		Map<String, Integer> map = new HashMap<>();
		
		for(int i =0 ; i < n ; i++) {
			map.put(input[i],i);
		}
		
		int ans =0 ;
		int [] output_idx = new int[n];
	
		for(int i =0 ; i  < output.length ; i++) {
			output_idx[i] = map.get(output[i]);
		}
		
		for(int i = output_idx.length-2 ; i >= 0 ; i--) {
			int previous = output_idx[i+1];
			int current = output_idx[i];
			
			if(previous < current)
				ans++;
			
			output_idx[i] = Math.min(previous, current);
		}
		
		System.out.println(ans);
	}

}