[백준] 2002 추월 - javascript

📌 문제

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

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const N = +input.shift();
const carInfo = input.map((i) => i.trim());
const visited = Array.from({ length: N }, () => false);
const map = new Map();

carInfo.slice(0, N).map((car, idx) => {
  map.set(car, idx);
});

let cur = 0;
let cnt = 0;

carInfo.slice(N).map((car) => {
  if (map.get(car) > cur) {
    let flag = false;
    for (let i = 0; i < map.get(car); i++) {
      if (!visited[i]) {
        flag = true;
        cnt++;
        break;
      }
    }
    if (!flag) cur = map.get(car) + 1;
  }
  visited[map.get(car)] = true;
});

console.log(cnt);

✔ 알고리즘 : 구현

✔ map 자료구조를 사용하여 차량정보가 들어오면 index를 해당 차량의 번호로 생각하여 저장하였다. (0~N-1)

✔ 해당 차량 번호가 터널을 빠져나갔는지 안나갔는지는 visited 배열을 통해 체크하였다.

✔ cur은 현재 통과되어야 할 차량번호이고 cnt는 추월한 차량의 수 이다.

✔ 나가는 차량의 정보를 받으면 차량 번호를 구하여 cur과 비교한다. 큰 경우 추월의 가능성이 있으므로 추월한 차인지 검사를 한다.

if (map.get(car) > cur) {
  let flag = false;
  for (let i = 0; i < map.get(car); i++) {
    if (!visited[i]) {
      flag = true;
      cnt++;
      break;
    }
  }
  if (!flag) cur = map.get(car) + 1;
}

for문은 추월로 인한 빠져나간 차들이 있는지 확인하여 현재 차량 정보가 cur보다 크더라도 추월을 안한 차량이 될 수 있는지 확인하는 반복문이다. 👉 하나라도 빠져나간 차가 없다면 현재 차량이 추월한 차량이된다. 👉 map.get(car) 즉, 차량번호와 cur 사이의 모든 차량이 이미 빠져나간 차인 경우에는 cur을 현재 차량번호보다 1크도록 설정해준다.

✔ 난이도 : 백준 기준 실버 1