[BOJ] 백준 2002 - 추월 풀이

1. 문제

https://www.acmicpc.net/problem/2002

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();
    }
}