1. 문제
https://www.acmicpc.net/problem/2002
2. 풀이
백준 알고리즘 카테고리에 구현으로 분류된 문제다.
입력은 차량의 수와, 들어온 차량의 번호가 순서대로 주어지고, 나간 차량의 번호가 순서대로 주어진다.
우리가 구해야 하는 것은 반드시 추월한 차량이 몇 대인지를 구하는 것이다.
예제 입력 1에서 힌트를 얻을 수 있다.
예제 입력 1을 보면 마지막으로 들어온 차량인 ZG206A가 모든 차량을 추월했다면, 나간 순서를 유지하고 예제 출력인 1을 만족한다.
이 힌트를 찾아내고 ArrayList로 문제를 해결하였다.
터널로 들어온 차량을 저장할 ArrayList와 나간 차량을 저장할 ArrayList를 각각 만든다.
입력을 받은 후 배열의 인덱스를 탐색하면서 반복문을 돌리는데, 들어온 차량의 번호와 나간 차량의 번호가 다르다면 들어온 차량의 ArrayList에서 나간 차량의 번호와 같은 것의 인덱스와 그 번호를 저장하고, 들어온 차량의 ArrayList에서 그 번호를 삭제 후 현재 반복문에서 탐색하고 있는 인덱스의 위치에 그 차량 번호를 넣어준다.
즉 예제 1번의 경우, 반복문의 탐색 인덱스가 0일 때 들어온 차량의 List는 ZG4315N이고 나간 차량의 List는 ZG206A이다.
들어온 차량의 List에서 ZG206A를 가지고 있는 곳의 인덱스를 찾고, 그 차량 번호를 저장한 후, 반복문의 탐색 인덱스가 0이므로, 들어온 차량의 List에서 ZG206A를 제거한 후 0번 위치에 ZG206A를 추가하면 나간 차량의 인덱스와 동일하게 배열된다.
이 과정을 하나로 치고 카운트를 세주면 답이 된다.
3. 소스 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int cnt = 0;
List<String> inputCar = new ArrayList<>();
List<String> outputCar = new ArrayList<>();
for (int i = 0; i < N; i++) {
inputCar.add(br.readLine());
}
for (int i = 0; i < N; i++) {
outputCar.add(br.readLine());
}
for (int i = 0; i < inputCar.size(); i++) {
if (!inputCar.get(i).equals(outputCar.get(i))) {
int index = inputCar.indexOf(outputCar.get(i));
String s = inputCar.get(index);
inputCar.remove(s);
inputCar.add(i, s);
cnt += 1;
}
}
bw.write(Integer.toString(cnt));
bw.flush();
bw.close();
br.close();
}
}