[백준 2002] 추월(JAVA)

백준 2002번 문제 - 추월

2002번: 추월

---

문제 분석 

 

 

• 들어가는 차량 순서와 나오는 차량 순서가 주어질 때, 추월한 차량 개수를 출력해라.

---

해결 포인트

 

• 해시맵 사용
• 들어온 차량 번호와 나오는 차량 번호를 배열로 저장
• 추월한 차량인 경우 맵에 저장 
  • 맵을 이용한 이유 : 맵에 해당 차량이 존재하는지 확인 시 시간 고려
• 들어온 차량을 확인하는 index(sIndex), 나간 차량을 확인하는 index(eIndex) 선언
  • 현재 확인하는 들어온 차량, 나간 차량이 동일 : sIndex++, eIndex++
  • 나간 차량이 추월한 차량 목록에 존재 : sIndex++
  • 위 경우가 다 아닌 경우 : eIndex++  (추월한 차량 목록에 추가 및 추월 차량 카운트 증가)

---

코드

 

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        String [] first = new String[N];
        for (int i = 0; i < N; i++) {
            first[i] = br.readLine();
        }

        String [] end = new String[N];
        for (int i = 0; i < N; i++) {
            end[i] = br.readLine();
        }

        Map<String, Boolean> goCar = new HashMap<>();

        int count = 0;
        int sIndex = 0, eIndex = 0;
        while(eIndex < N && sIndex < N) {
            if(first[sIndex].equals(end[eIndex])) {
                sIndex++;
                eIndex++;
            }
            else if(goCar.containsKey(first[sIndex])) {
                sIndex++;
            }
            else {
                count++;
                goCar.put(end[eIndex], true);
                eIndex++;
            }
        }

        bw.write(count + "\n");

        bw.flush();
        bw.close();
    }
}