[백준] 2002번 : 추월 – JAVA [자바]

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

2002번: 추월

 

---

• 문제

 

 

---

• 문제 풀이

백준 2002번 추월은 실버 1 난이도의 자료 구조 및 문자열 문제이다. 

 

이 문제에서는 차의 대수 N이 주어진다. 그리고 터널에 들어간 차 N대와 터널에서 나온 차 N대가 주어진다. 이때, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력하면 된다.

 

이 문제를 풀기 위해서는 '추월'이라는 것을 정의해야 한다. 차가 추월을 하려면 앞에 있었던 차보다 더 빨리 터널에서 나와야 한다.

 

예를 한 번 들어보겠다. 터널에 들어갈 때는 A B C D 순서로 들어갔다고 가정을 해보겠다. 그리고 터널에서 나왔을 때는 A B D C 순서대로 나왔다고 하겠다. 여기서 C를 보면 처음에 C 앞에 A 하고 B가 있었고 터널에서 나왔을 때도 A 하고 B가 있었다. 즉, C는 추월을 하지 않았고 여기서 D만 C를 추월했다.

 

여기서 볼 수 있듯이 추월이란 차 앞에 있었던 차들이 터널에서 나왔을 때 단 한대로 앞에 없으면 추월이라고 한다.

 

우선 리스트 2개를 만든다. 리스트 in은 터널에 들어갈 때의 차들의 순서고 리스트 out은 터널에서 나왔을 때의 차들의 순서이다. 

 

우선, 이 풀이에서는 리스트 클래스에 있는 subList(int fromIndex, int toIndex) 함수와 containsAll(Collections) 함수를 이용할 것이다. 

 

입력을 받고 나면 리스트 out에 있는 차들을 순서대로 처리해준다. 우선, out에 있는 i번째 차를 C라고 하겠다. 이 차를 처리할 때 i번째 차 이전에 있는 차들을 모두 리스트로 만들어준다. 즉, out.subList(0, i)를 해준다. 

 

그리고, 리스트 in에서도 C 이전에 있었던 차들을 모두 리스트로 만들어준다. 즉, in.subList(0, in.indexOf(out.get(i)))를 해준다. 

 

이러면 터널에 들어갈 때 C 이전에 있었던 차들과 터널에서 나왔을 때 C 이전에 있었던 차들을 리스트 형태로 보관하고 있다. 이제, 터널에 들어갈 때 C 이전에 있었던 차들이 터널에서 나왔을 때도 C 이전에 있었는지를 확인해 주면 된다. 이건 containsAll() 함수를 이용해서 확인해준다. 만약에, 단 한대로 C 이전에 없다면 C가 그 차를 추월했다는 것이다.

 

자세한 코드는 아래에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 차량 대수 N을 입력 받음
        List<String> in = new ArrayList<>(); // 대근이의 차량 번호 기록을 저장할 리스트
        for (int i = 1; i <= n; i++) {
            in.add(br.readLine()); // 대근이의 차량 번호 기록을 입력 받아 리스트에 추가
        }
        List<String> out = new ArrayList<>(); // 영식이의 차량 번호 기록을 저장할 리스트
        for (int i = 1; i <= n; i++) {
            out.add(br.readLine()); // 영식이의 차량 번호 기록을 입력 받아 리스트에 추가
        }
        int count = 0; // 추월이 발생했을 것으로 예상되는 차량 대수를 저장할 변수
        for (int i = 0; i < n; i++) {
            List<String> inBefore = in.subList(0, in.indexOf(out.get(i))); // 대근이의 현재 차량 기록 이전 부분을 sublist로 가져옴
            List<String> outBefore = out.subList(0, i); // 영식이의 현재 차량 기록 이전 부분을 sublist로 가져옴

            // 대근이의 이전 차량 기록 부분이 영식이의 이전 차량 기록 부분에 모두 포함되지 않으면 추월이 발생한 것이므로 count를 증가시킴
            if (!outBefore.containsAll(inBefore)) {
                count++;
            }
        }
        System.out.println(count); // 추월이 발생했을 것으로 예상되는 차량 대수를 출력

    }

}

 

---

• 코드 2: 해시맵