[백준] 추월 (2002) - Java

 

---

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

2002번: 추월

---

[문제 설명]

터널에 내부에서 추월한 차량의 대수를 출력하는 문제입니다.

 

문제를 더욱 쉽게 직관적으로 이해하기 위해 그림으로 설명 드리겠습니다.

 

[a, b, c, d]의 자동차들이 순서대로 터널에 진입을 하게 됩니다.

 

 

[자동차들이 화살표 방향으로 터널 진입]

그 후

 

아래의 그림과 같이 차량들이 터널을 빠져 나오게 되며, [d, a, c, b] 차량 순으로 차가 빠져 나오게 됩니다.

 

d, c 차량이 추월을 한 경우이므로 추월한 차량은 총 2대가 됩니다.

[화살표 방향으로 차가 빠져 나옴]

---

[문제 해결]

자 그럼 문제를 어떻게 해결해야 할까요?

저 같은 경우는 터널을 입장하는 차량에 순번을 매겨준 후 기존 앞 차량보다 먼저 나왔으면 추월한 차량으로 판단했습니다.

 

자 이게 무슨 소리냐?

 

터널을 입장할때의 차량 순번들은 [a - 1, b - 2, c - 3, d - 4] 인데 

가장 먼저 나온 d 차량의 순번 4가 그 뒤에 나오는 a 차량 순번 1보다 높으므로 추월한 것으로 간주 하는 것입니다.

 

그림으로 설명해 드리겠습니다.

 

d의 숫자가 a의 숫자보다 높으므로 추월한 차량

d의 차량은 비교가 끝났으니 지워주고 바로 뒤에 나오는 a의 차량을 기준으로 비교를 해줍니다.

비교를 해 보았더니 a차량은 어느 뒤 차량보다 숫자가 낮으므로 추월한 차량이 아닙니다.

a 차량이 추월한지 안한지 판별이 났으니 지워주고 c차량 기준으로 뒤 차들이랑 비교를 해줍니다.

c 차량의 순번이 뒤 차량 b의 순번보다 높으니 c는 추월한 차량으로 간주 됩니다.

 

이렇게 되면 추월한 차량은 d, c 총 2대가 됩니다.

 

---

자 그럼 코딩을 어떻게 해야할까요?

 

1. 위 그림 같이 차량의 이름 - 순번으로 데이터를 저장하기 위해 해쉬 맵으로 저장합니다.
2. 저장된 해쉬 맵의 제일 앞 요소를 기준으로 뒷 요소들과 비교해줍니다.
3.  앞 요소가 뒷 요소보다 숫자가 높다면 추월한 것으로 판단하고 pass Count를 해줍니다.
4. 앞 요소의 비교가 끝나면 앞 요소를 제거 해준다.
5.  마지막 요소까지 1-4번 과정을 반복

• 여기서 주의 하실점은 일반 HashMap으로 저장하게 된다면 요소들이 순서를 지키지 않으므로 LinkedHashMap을 사용 하셔야 합니다.

 

[정답 코드 - Java] 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedHashMap;


public class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int carNum = Integer.parseInt(br.readLine());
        LinkedHashMap <String, Integer> inCar = new LinkedHashMap<>();

        for(int i=1; i<=carNum; i++) inCar.put(br.readLine(), i);

        int pass = 0;
        for(int i=1; i<=carNum; i++){
            String outCar = br.readLine();

            Iterator<String> it = inCar.keySet().iterator();
            while(it.hasNext()){
                if(inCar.get(outCar) > inCar.get(it.next())){
                    pass++; break;
                }
            }

            inCar.remove(outCar);
        }

        System.out.println(pass);
    }

}