[Softeer] 교차로 JS (큐, 구현)

https://softeer.ai/practice/6256

 

자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 직진만 가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로를 통과할 수 있다. 자동차들이 동시에 교차로를 통과하면 충돌할 수 있기 때문에, 효율적인 도로 교통 흐름을 위해서는 자동차끼리의 충돌을 방지할 수 있도록 자동차가 적절히 멈춰 있도록 하되, 너무 오래 멈춰 있지 않도록 소프트웨어를 적절하게 작성해야 한다.

이 문제에서 각 도로의 맨 앞에 있는 자동차는 자신을 기준으로 오른쪽에 위치한 도로에 차량이 있으면 1초 동안 출발하지 않고, 차량이 없으면 즉시 교차로를 통과한다. A 위치에 있는 차량의 오른쪽에 있는 도로는 D 위치의 도로이고, B 위치에 있는 차량의 오른쪽에 있는 도로는 A 위치의 도로이고, C 위치에 있는 차량의 오른쪽에 있는 도로는 B 위치의 도로이고, D 위치에 있는 차량의 오른쪽에 있는 도로는 C 위치의 도로이다. 정확한 설명을 위해 아래와 같은 상황을 생각하여 보자.

1번 차량이 C 위치에, 2번 차량이 B 위치에 있다. 두 차량이 동시에 출발하게 되면 왼쪽 그림과 같이 교차로 위에서 충돌할 우려가 있다. 1번 차량을 기준으로 오른쪽에 있는 도로인 B 위치의 도로에 차량이 있기 때문에, 1번 차량은 1초간 출발하지 않고, 2번 차량은 교차로를 통과한다.

위와 같이 1번 차량이 다른 차량이 지나갈 때까지 대기하는 동안 새로운 차량이 C 위치에 계속 진입할 수 있다. 차선이 하나밖에 없기 때문에, 맨 앞에 있는 차량이 지나가기 전까지는 해당 위치의 차선에 적체된 차량이 계속 늘어날 수 있다. 예를 들어 위의 상황에서 1초 뒤에 3번 차량이 B번 위치에, 4번 차량이 C번 위치에 진입할 경우, 아래와 같이 C번 위치에 1번 차량과 4번 차량이 대기하게 된다.

안전을 위해 각 위치마다 1초에 한 대씩만 교차로를 통과할 수 있다. 위의 그림과 같이 하나의 차선에 1번 차량과 4번 차량이 서 있고 이후에 차량이 새로 진입하지 않는다면, 1초 뒤에 1번 차량이 교차로를 통과하고, 다시 1초 뒤에 (전체적으로 2초 뒤에) 4번 차량이 교차로를 통과할 것이다.

A, B, C, D 위치에 동시에 차량이 한 대 이상씩 있다면, 교착 상태에 빠져 어떤 차량도 교차로를 통과할 수 없게 된다. 앞으로 N대의 차량이 교차로를 통과하기 위해 A, B, C, D 위치에 진입할 것이다. i (1 ≤ i ≤ N)번 차량은 ti초 때에 wi 위치에 진입하여, 해당 차선에 있는 줄 맨 뒤에 있을 예정이다. 혼선을 방지하기 위해, 같은 시각에 각 위치에 진입할 수 있는 차량은 최대 한 대이다.

매초마다 모든 차량이 진입한 직후, 각 위치의 맨 앞에 있는 차량은 오른쪽 위치에 차량이 없는지 확인한 뒤, 차량이 없다면 교차로를 통과한다. 각 차량이 교차로를 통과하는 시각이 언제인지 계산하는 프로그램을 작성하라.

제약조건

2 ≤ N ≤ 200,000
모든 i(1 ≤ i ≤ N)에 대해, 0 ≤ ti ≤ 109이고, wi는 A, B, C, D 중 하나이다.
t1 ≤ t2 ≤ ... ≤ tN

i ≠ j 이고 ti = tj이면, wi ≠ wj이다.

입력형식

첫 번째 줄에 N이 주어진다. 다음 N개의 줄 중 i (1 ≤ i ≤ N)번째 줄에는 ti와 wi가 공백 하나를 사이로 두고 주어진다.

출력형식

첫 번째 줄에 N개의 정수를 공백 하나씩을 사이로 두고 출력한다. 이 중 i (1 ≤ i ≤ N)번째 정수는 i번 차량이 도로를 통과한다면 교차로를 통과하는 시각, 교차로를 통과하지 않는다면 -1이어야 한다.

---

 

 

문제요점

오른쪽에 차 있으면 1초 기다림
교차로는 1대만 통과 1초걸림
n대 차량, t초, w위치
각 차량이 교차로를 통과하는 시각 출력

 

첫번째 풀이 (시간초과)

입력값을 순회하며 A,B,C,D 각각의 큐에 차를 넣는다. 이 때 정답에서 index마다 time을 출력하길 요구하므로 {인덱스, 도로에 들어온 시각}을 넣는다.

현재시각 = 맨 처음 차가 도로에 있는 시각부터 시작하여, 교착상태이거나 차가 모두 통과 할 때까지 while문을 돈다.

 

A,B,C,D 각 큐의 첫번째 차들 중 도로에 들어선 시각이 현재시각보다 작거나 같으면 해당 차들은 carsOnTheRoad 배열에 기록한다. 이 차들 중 오른쪽에 다른 차가 없을 시에 통과시키고 currTime을 1초 증가시킨다. 이때 통과된 차들은 기존의 큐에서 제거한다.

 

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdoutg
})

const line = [];

rl.on('line', input => {
  line.push(input.split(' ').map(e => {
      if (!isNaN(e)) return parseInt(e);
      return e;
  })); 
})

rl.on('close', () => {
    const n = line.shift();
    const answer = Array.from({length: n}, () => -1); // 각 차량이 통과하는 시각
    const queues = [[], [], [], []]; // a,b,c,d 큐
    const roadIndex = {'A': 0, 'B': 1, 'C': 2, 'D': 3};

    for (let i = 0; i < line.length; i++) {
        const [enterTime, road] = line[i];
        if (road === 'A') {
            queues[0].push({i, enterTime: Number(enterTime), road: 'A'});
        } else if (road === 'B') {
            queues[1].push({i, enterTime: Number(enterTime), road: 'B'});
        } else if (road === 'C') {
            queues[2].push({i, enterTime: Number(enterTime), road: 'C'});
        } else if (road === 'D') {
            queues[3].push({i, enterTime: Number(enterTime), road: 'D'});
        }
    }
    let currTime =  line[0][0] // 맨 처음으로 차가 도로 위에있는 시간
    
    function getCarsOnRoad() {
        const result = []
        for (const queue of queues) {
            if (queue.length) {
                if (queue[0].enterTime <= currTime) {
                    result.push(queue[0]);
                }
            }
        }
        return result;
    }

    function hasRightCar(currRoad, roads) {
        const rightObj = {
            'A': 'D',
            'B': 'A',
            'C': 'B',
            'D': 'C'
        }
        return roads.includes(rightObj[currRoad]);
    }
    while(1) {
        const carsOnTheRoad = getCarsOnRoad() // 도로위의 차들 구하기
        // 교착상태이거나 더이상 차가 없으면 끝
        if (carsOnTheRoad.length === 4 || queues.reduce((acc, curr) => {
            acc += curr.length
            return acc;
        }, 0) === 0) {
            break;
        } 
        // 오른쪽에 차가 없어서 지금 갈수 있는 차들
        const roadTypesHasCar = carsOnTheRoad.map(e => e.road);
        const carsCanGo = [];
        for (const car of carsOnTheRoad) {
            if (!hasRightCar(car.road, roadTypesHasCar)) {
                carsCanGo.push(car);
            }
        }
        // 차들 통과시키기
        carsCanGo.forEach(car => {
            const {i, road} = car;
            queues[roadIndex[road]].shift(); // 큐에서 통과한 차 삭제하기
            answer[i] = currTime;
        })
        // 시간 추가
        currTime++;
    }
    answer.forEach(e => console.log(e))
    process.exit();
})

 

---

 

두번째 풀이 (큐 구현, 불필요한 시간패스)

 

0 ≤ ti ≤ 10^9이라서 currTime을 1초씩 늘리면 당연히 시간초과가 난다

또한 2 ≤ N ≤ 200,000 이여서 O(n^2)되는 shift를 사용할 수 없다

 

 

남은 차가 있지만 현재 시각에 도로 위에 있는 차가 없을 시 바로 다음 차가 들어오는 시각으로 넘어가버린다.

// 남은 차가 있는데, 도로위에 차가 없으면 가장 빠른 다음 시간으로 타임슬립
if (isCarRemained() && !carsOnTheRoad.length) {
  const nextTimesOfEachRoad = []; // 각 길마다 다음시간
  for (const queue of queues) {
    if (queue.size) {
      const first = queue.getFirst();
      nextTimesOfEachRoad.push(first.enterTime);
    }
  }
  nextTimesOfEachRoad.sort((a, b) => a - b);
  currTime = nextTimesOfEachRoad[0];
  continue;
}

 

 

+ 큐를 구현하니 통과했다.

 

전체코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdoutg,
});

const line = [];

rl.on("line", (input) => {
  line.push(
    input.split(" ").map((e) => {
      if (!isNaN(e)) return parseInt(e);
      return e;
    })
  );
});

rl.on("close", () => {
  const n = line.shift();
  const answer = Array.from({ length: n }, () => -1); // 각 차량이 통과하는 시각
  const queues = [new Queue(), new Queue(), new Queue(), new Queue()];
  const roadIndex = { A: 0, B: 1, C: 2, D: 3 };

  for (let i = 0; i < line.length; i++) {
    const [enterTime, road] = line[i];
    if (road === "A") {
      queues[0].enqueue({ i, enterTime: Number(enterTime), road: "A" });
    } else if (road === "B") {
      queues[1].enqueue({ i, enterTime: Number(enterTime), road: "B" });
    } else if (road === "C") {
      queues[2].enqueue({ i, enterTime: Number(enterTime), road: "C" });
    } else if (road === "D") {
      queues[3].enqueue({ i, enterTime: Number(enterTime), road: "D" });
    }
  }
  let currTime = line[0][0]; // 맨 처음으로 차가 도로 위에있는 시간

  function getCarsOnRoad() {
    const result = [];
    for (const queue of queues) {
      if (queue.size) {
        const first = queue.getFirst();
        if (first.enterTime <= currTime) {
          result.push(first);
        }
      }
    }
    return result;
  }

  function hasRightCar(currRoad, roads) {
    const rightObj = {
      A: "D",
      B: "A",
      C: "B",
      D: "C",
    };
    return roads.includes(rightObj[currRoad]);
  }
  function isCarRemained() {
    return (
      queues.reduce((acc, queue) => {
        acc += queue.size;
        return acc;
      }, 0) > 0
    );
  }
  while (1) {
    const carsOnTheRoad = getCarsOnRoad(); // 도로위의 차들 구하기
    // 남은 차가 있는데, 도로위에 차가 없으면 가장 빠른 다음 시간으로 타임슬립
    if (isCarRemained() && !carsOnTheRoad.length) {
      const nextTimesOfEachRoad = []; // 각 길마다 다음시간
      for (const queue of queues) {
        if (queue.size) {
          const first = queue.getFirst();
          nextTimesOfEachRoad.push(first.enterTime);
        }
      }
      nextTimesOfEachRoad.sort((a, b) => a - b);
      currTime = nextTimesOfEachRoad[0];
      continue;
    }
    // 교착상태이거나 더이상 차가 없으면 끝
    if (carsOnTheRoad.length === 4 || !isCarRemained()) {
      break;
    }
    // 오른쪽에 차가 없어서 지금 갈수 있는 차들
    const roadTypesHasCar = carsOnTheRoad.map((e) => e.road);
    const carsCanGo = [];
    for (const car of carsOnTheRoad) {
      if (!hasRightCar(car.road, roadTypesHasCar)) {
        carsCanGo.push(car);
      }
    }
    // 차들 통과시키기
    carsCanGo.forEach((car) => {
      const { i, road } = car;
      queues[roadIndex[road]].dequeue(); // 큐에서 통과한 차 삭제하기
      answer[i] = currTime;
    });
    // 시간 추가
    currTime++;
  }
  answer.forEach((e) => console.log(e));
  process.exit();
});

class Node {
  constructor(n) {
    this.value = n;
    this.next = null;
  }
}

class Queue {
  constructor(list) {
    this.head = null;
    this.p = this.head;
    this.size = 0;
  }

  enqueue(n) {
    const newNode = new Node(n);
    if (!this.head) {
      this.head = newNode;
      this.p = newNode;
    } else {
      this.p.next = newNode;
      this.p = this.p.next;
    }
    this.size++;
  }

  dequeue() {
    if (!this.head) return null;
    const removed = this.head;
    this.head = this.head.next;
    this.size--;
    return removed;
  }

  getSize() {
    return this.size;
  }

  getQueue() {
    if (this.size === 0) return false;
    const result = [];
    let p = this.head;
    while (p) {
      result.push(p.val);
      p = p.next;
    }
    return result;
  }

  getFirst() {
    return this.head.value;
  }
}

 

 

 

 

 

 

 

 

 

 

참고

https://smartshk.tistory.com/51