[알고리즘] 백준 2002번 : 추월 (실버1)

 

 

문제

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

 

✔ 풀이 설명

터널 전 랭킹인 기준 배열과 터널 후 랭킹 배열을 만든다.

기준 차량을 먼저 정한다. 기준 차량은 기준 배열에서 0이 아닌 값 중에서 가장 작은 값을 의미한다.
현재 기준 차량은 1등이다. 기준 차량이 터널 후 랭킹에서 몇 번째로 달리고 있는지 터널 후 랭킹 배열에서 찾는다.
기준 차량이 터널 후 랭킹에서 3번째로 달리고 있다. 즉, 기준 차량 앞에 있는 모든 차량은 다 추월 차량이다.

기준 차량 앞에 있는 모든 차량은 추월 차량이므로 체크 표시를 넣었다.

기준 차량 앞에 있는 5등 차량과 2등 차량은 추월 차량이므로 기준 배열에서 값을 0으로 초기화 했다.

또 새로운 기준 차량을 기준 배열에서 찾는다. 원래는 2등이어야 하지만 2등은 추월 차량이므로 기준 배열에서 탈락했다. 그러므로 나머지 등수 중에서 가장 작은 수인 3등이 기준 차량이다.
기준 차량인 3등이 터널 후 랭킹에서 마지막 번째로 달리고 있다.

기존의 기준 차량인 1등과 새로운 기준 차량인 3등 사이에서 달리는 차량은 모두 추월 차량들이다.
4등 차량이 추월 차량이므로 체크 표시를 넣어줬다.

기준 배열 값들이 모두 0으로 됐고 모든 차량 조사가 끝났다. 압정 표시가 있는 차량들이 추월 차량들이다.
총 3대가 추월했다.

 

📌 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());

		Map<String, Integer> map = new HashMap<>();
		
		// 터널 전 랭킹
		for(int i=0; i<N; i++) {
			map.put(br.readLine(), i+1);
		}
		
		// 기준점 배열
		int[] criterionArr = new int[N];
		
		for(int i=0; i<N; i++) {
			criterionArr[i] = i+1;
		}

		// 터널 후 랭킹
		int[] afterRanking = new int[N];
		
		for(int i=0; i<N; i++) {
			afterRanking[i] = map.get(br.readLine());
		}
		
		int criterion = 0; // 기준 차량
		
		boolean check = true;  // 기준 차량 찾기 유무
		
		int count = 0; // 추월 차량 수
		
		for(int i=0; i<N; i++) {
			
			// 기준 점 찾기
			if(check) {
				for(int k=0; k<criterionArr.length; k++) {
					criterion= criterionArr[k];
					if(criterion!=0) break;  // 기준 배열에서 가장 작은 수 찾기
				}
			}
			
			check = false;  // 기준 차량 찾기 off

			int idx = afterRanking[i]-1;
			criterionArr[idx] = 0;
			
			if(afterRanking[i]!=criterion) { 
				count++;
				continue;
			}		

			check = true; // 기준 차량 찾기 on
		}
		
		bw.write(String.valueOf(count));
		bw.close();
		
	}
}