백준 2002 <추월>

생각하는 것에 따라 어려움과 그렇지 않음으로 나눠지는 문제 같다.

 

들어가는 차량이라면 이름이 처음 등장할 것이고 나오는 차량이라면 두 번째로 등장할 것이다.

 

이점을 유의해서 자기 차례에 자신의 차가 아니고 다음차량이 나오는 개수를 세주면 되는 문제이다.

 

자기 들어가는 차량이 몇번짼지 체크해주기 위해서 hashmap을 사용했고 key는 차 이름 value는 몇 번 짼 지를 넣어주었다.

 

풀이 순서

1. 처음 등장한다면 hashmap에 차이름과 순서를 넣어준다.
2. 시작 순서는 0번 부터 시작하고 hashmap에 있는 차가 또 나오면 순서를 확인하고 이후 번호면 count를 해준다. 이때 visit 배열에 방문처리를 함으로써 이미 나온 것을 표시해준다.
3. 자신이 차례가 맞으면 나오지않은 순서중 다음 순서로 옮겨준다.

 

자동차가 1 2 3 4 5 순서대로 들어간다.

3번 차량이 먼저 나가게 되면 현재 위치보다 크기 때문에 result를 1 더해주고 나갔다는 표시를 해준다.

다음에 순서대로 1번 차량이 나갔기 때문에 방문처리를 함과 동시에 이후에 방문 안 한 다음 번호로 이동

 

이런 식으로 시뮬레이션을 그려보면 흐름을 파악하기 쉬울 것이다.

 

전체 코드

package solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;

public class Main {

	static HashMap<String,Integer> ha;
	static int n;
	static boolean visit[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int point=0,plus=0;
		int result=0;
		n=Integer.parseInt(br.readLine());
		visit=new boolean[n];
		ha=new HashMap<String,Integer>();
		while(point<n) {
			String s=br.readLine();
			if(ha.get(s)!=null) {
				if(point!=ha.get(s)) {
					visit[ha.get(s)]=true;
					result++;
				}
				else {
					visit[point]=true;
					while(visit[point]) {
						point++;
						if(point==n) {
							break;
						}
					}
				}
			}
			else {
				ha.put(s,plus++);
			}
		}
		System.out.println(result);
	}

}