[BOJ] 2002 추월

MY TMI 😉

 

📑

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

2002번: 추월

자동차 수 N이 주어지고, 처음 N개는 터널에 들어간 순서대로 / 이후 N개는 터널에서 나온 순서대로 입력된 것이다.

입력 예시

터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들의 개수를 구하는 것이 이 문제의 목표이다. 

 

✔ 추월의 기준

☝ '나'의 번호보다 앞 번호인 차들이 내 뒤에 있을 경우, '나'는 앞 차들을 추월한 것이다. 

 

➡ 처음 N개의 차량 번호 목록을 입력받은 후, 이를 해시맵을 이용하여 key를 차량 번호, value를 고유 번호로 지정하여 순서들을 관리하였다. 

➡ 차량 개수만큼의 boolean 배열을 생성하여 내 앞차들이 나갔는지 안나갔는지를 체크할 수 있게 한다.

➡ 이후 차량 번호를 입력받을 때마다 내 고유번호보다 앞 번호의 차들이 나갔는지 나가지 않았는지 확인한다. 

☝ 모두 나갔다면 (모두 T) : 나는 내 앞 차들을 추월한 것이 아니다❗

✌ 하나라도 나가지 않았다면 : 나는 내 앞 차 중 적어도 하나를 추월한 것이다 ➡ 추월 차량 카운트 증가❗

 

이러한 흐름으로 문제를 해결하였다. 

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

/**
 * BOJ 2002 추월
 * 2021.07.05
 * : 해시맵 & boolean 배열 사용 ==> 내 숫자보다 앞인 애들이 아직 안나갔다면 추월했다는 의미!
 * @author 0JUUU
 *
 */

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		HashMap<String, Integer> carList = new HashMap<>();
		for(int i = 0; i<N;i++) {
			String carName = br.readLine();
			carList.put(carName, i);
		}
		
		int cnt = 0;
		boolean[] isOut = new boolean[N];
		for(int i = 0; i<N;i++) {
			String carName = br.readLine();
			int num = carList.get(carName);
			for(int j = 0; j<num;j++) {
				if(!isOut[j]) {
					cnt++;
					break;
				}
			}
			isOut[num] = true;
		}
		System.out.println(cnt);
	}
}