2002 - 추월 (Java)

 

---

 

문제

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

 

 

풀이

추월의 요점을 잘 생각해봐야한다.

 

난 처음에 들어가는 순서보다 나오는 순서가 빠른 순으로만 생각했는데 바로 틀렸다.

 

요는, 내 뒤에 있던 차량이 내 앞으로 갔는가? 이다.

 

게시판에 반례가

 

a        d

b        a

c        c

d        b

 

가 있었다. (왼쪽 줄이 들어간 순서, 오른쪽 줄이 나온 순서)

 

나오는 순서대로 체킹하면 d 하나만 체크가 될 것이다.

 

그러나 내 뒤에 있던 차량이 내 앞으로 간 것을 체크하면 d 와 c 2개가 있다.

 

우선 차량이 들어온 순서대로 리스트로 데이터를 받는다.

 

나가는 순서는 해쉬맵을 이용해서 <자동차 번호, 나가는 순서> 로 저장한다.

 

해쉬맵을 이용하지 않으면 리스트에서 내 뒤에 있는 차량이 내 앞에 있는지 리스트를 다 순회해야한다.

그러면 시간초과가 날 것이다.

 

그러니 이중 for문을 돌려서 내 뒤에 있는 차량들이 나올때는 내 앞에 있는지는 해쉬를 이용해서 확인하는 것이다.

 

a b c d 라고 하면

 

a 를 기준으로, b 라는 차가 내뒤에 있었는데

 

hash(a) 와 hash(b) 를 비교해서 b가 나보다 앞에 나오진 않았는지 검사하는 것이다. (hash(a) 는 a의 나온 순서이다.)

 

그렇게 먼저 나온 값들을 중복을 피하기 위해 set에 저장한다음 set의 사이즈를 출력하면 된다.

 

코드

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

/**
 * [문제] (https://www.acmicpc.net/problem/2002)
 */

public class Main {

    public static Integer numOfCars;
    public static Map<String, Integer> exitHistory = new HashMap<>();
    public static List<String> seqOfCars = new ArrayList<>();
    public static Set<String> carSet = new HashSet<>();

    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        numOfCars = Integer.parseInt(br.readLine());

        for (int i = 0; i < numOfCars; i++) seqOfCars.add(br.readLine());
        for (int i = 0; i < numOfCars; i++) exitHistory.put(br.readLine(), i);

        for (int i = 0; i < numOfCars-1; i++) {
            String mainCar = seqOfCars.get(i);
            for(int j=i+1; j < numOfCars; j++){
                String subCar = seqOfCars.get(j);

                // subCar 가 나올때 나보다 앞에 있는지를 검사한다.
                if (exitHistory.get(mainCar) > exitHistory.get(subCar)) {
                    carSet.add(subCar);
                }
            }
        }

        System.out.println(carSet.size());
    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

문제 예제는 나온 순서만 체크해도 맞길래 그냥 넣었는데 바로 틀렸었다. 알면 쉽지만 까딱하면 틀리기 좋은 문제 아닐까..