백준 2002 (추월)

문제

---

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

 

 

 

 

풀이

---

HashMap을 이용한 문제였다.

 

1. HashMap을 이용하여 처음 들어가는 순서를 차번호와 순서를 미리 저장해둔다.
2. 나가는 차의 차번호를 확인하여, 나가는 순서의 배열위치에 들어갈때의 순서를 저장한다.
3. 나가는 순서의 차가 들어갈때 자신보다 앞서 있었던 차보다 먼저나가면 추월한 것이다.

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bufferedReader.readLine());
		HashMap<String, Integer> carEnter = new HashMap<String, Integer>();
		
		
		for(int i = 0 ; i < n ; i++) {
			String carNumber = bufferedReader.readLine();
			carEnter.put(carNumber, i);
		}
		
		int count = 0;
		int[] out = new int[n];
		for(int i = 0 ; i < n ; i++) {
			String carNumber = bufferedReader.readLine();
			out[i] = carEnter.get(carNumber);
		}
		
		for(int i = 0 ; i < n - 1 ; i++) {
			for(int j = i + 1 ; j < n ; j++) {
				if(out[i] > out[j]) {
					count++;
					break;
				}
			}
		}
		System.out.println(count);
	}
}