[백준] 2002 추월 - HashMap(해시맵) + 구현(Implementation) JAVA

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

2002번: 추월

코드설명

HashMap(해시맵) + 구현(Implementation) 문제입니다.

 

HashMap에는 ("차이름", 순서) 로 적용합니다.

문제의 예시로들어보면, 아래와 같습니다.

 

ZG431SN - 0번째차량
ZG5080K - 1번째차량
ST123D - 2번째 차량
ZG206A - 3번째 차량

 

터널 안에서 먼저 나간, 즉 추월한 차량은 어떻게 판단할 수 있을까요?

 

만약 나가는 차량의 들어온 순서보다, 아직 터널 안에 있는 차량 중 1개라도 들어온 순서가 더 크다면 추월한 것으로 판단할 수 있습니다.

 

즉, Z6206A - 3 차량이 나갈때 터널에는 여전히 ZG431SN - 0 번째 차량이 남아있으므로, Z6206A 는 추월한것으로 판단할 수 있습니다.

그리고 해당 차량이 나갔다면, 해당 차량을 HASHMAP에서 삭제시켜주어 갱신시킵니다.

 

만약 HASHMAP을 사용하지 않았다면, 따로 차량의 위치를 iNDEX로 관리해야해서 불필요하거나, O(N^2)의 시간복잡도가 걸리는 순회하여 확인하는 방법을 사용해야했습니다.

HASHMAP을 활용하여 조회복잡도를 줄입니다.

코드

package algorhythm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, T;
	public static HashMap<String, Integer> tunnelInCarHashMap = new HashMap<>();
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		
		//먼저 들어가는 차량입니다.
		int cnt = 0;
        // ZG431SN - 0번째차량
		// ZG5080K - 1번째차량
		// ST123D - 2번째 차량
		// ZG206A - 3번째 차량
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String car = st.nextToken();
			tunnelInCarHashMap.put(car, cnt++);
		}
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String outCar = st.nextToken();
			
			//만약 어느 한 숫자라도 현재 나가는 car보다 번호가 작은것이 존재한다면, 해당 차량은 추월한 것 입니다.
			//나와 같은것이 나와도 신경쓰지않아도됩니다.
			for(Entry<String,Integer> entrySet : tunnelInCarHashMap.entrySet()) {
				//나보다 더 작은숫자가 아직 터널에 존재하는경우.
				if(tunnelInCarHashMap.get(outCar) > entrySet.getValue()) {
					answer += 1; break;
				}
			}
			tunnelInCarHashMap.remove(outCar);
		}
		System.out.println(answer);
	}
}

 

코드 2입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static int[] arr;
	public static HashMap<String, Integer> hashmap = new HashMap<>();
	public static Node[] input, output;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		input = new Node[N]; 
		output = new Node[N];
		
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			hashmap.put(str, i);
			input[i] = new Node(str, i);
		}
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			output[i] = new Node(str, hashmap.get(str));
		}
		
		for(int i=0; i<N; i++) {
			int idx = hashmap.get(output[i].str);
			for(int j=i+1; j<N; j++) {
				if( idx > output[j].idx) {
					answer += 1;
					break;
				}
			}
			hashmap.remove(output[i].str);
		}
		System.out.println(answer);
		
	}
}
class Node{
	String str;
	int idx;
	public Node(String str, int idx) {
		this.str = str;
		this.idx = idx;
	}
}