<자료 구조> BOJ 2002 추월

문제

터널에 들어간 순서와 나온 순서가 같아야 한다. 즉 추월을 해서는 안된다. 들어간 순서와 나온 순서를 알고 있을 때 반드시 추월한 차량의 수를 구하는 문제

접근

1. 들어간 차량의 번호판과 순서를 각각 key 값과 value로 HashMap에 저장한다.
2. 나온 차량의 순서를 index로 번호판을 배열에 저장한다.
3. 모든 차량에 대해 나올 때 뒤에 있던 차가 들어갈 때는 앞에 있던 경우가 하나라도 확인된다면 정답에 1 추가

잘못된 접근

1. 들어간 차량의 번호판과 뒤에 있는 차량의 수를 각각 key 값과 value로 HashMap에 저장한다.
2. 나오는 차량에 대해 추월 여부를 아래와 같이 판단한다.

• 현재 뒤에 있는 차량의 수가 (기존 뒤에 있는 차량의 수 - 추월한 차량의 수)보다 크다면 추월 차량으로 판단하고 추월 차량의 수 1 추가

근데 이 접근 방법은 틀리는데 정확한 이유를 모르겠습니다. 틀린 논리를 찾으면 이유도 추가하겠습니다.

코드

import java.io.*;
import java.util.*;

class baek__2002 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            map.put(br.readLine(), i);
        }

        String[] out = new String[n];
        int pass = 0;

        for (int i = 0; i < n; i++) {
            out[i] = br.readLine();
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (map.get(out[i]) > map.get(out[j])) {
                    pass++;
                    break;
                }
            }
        }

        System.out.print(pass);
    }
}