[백준] 2002 추월 - Data Structure / Java

• 문제 링크

2002번: 추월

 

• 풀이 과정

차량별 진입 순서를 Map에 저장하고, 출구에서 나온 차량의 진입 순서를 배열에 저장한다.

 

만약 출구에서 나온 차량의 진입 순서가 이후에 나온 차량보다 크다면 이는 추월한 차량이므로

이때 카운트를 증가시키는 방식으로 추월한 차량의 개수를 구한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;

public class Main {

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

        int n = Integer.parseInt(br.readLine());

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++)
            map.put(br.readLine(), i);

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = map.get(br.readLine());


        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    cnt++;
                    break;
                }
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
    }

}