[Javascript/자바스크립트] 백준 13335번 트럭

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

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";

const [n, w, l, ...arr] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(/\s/)
  .filter((item) => item != "")
  .map((item) => +item);

class TruckNode {
  constructor(weight) {
    this.next = null;
    this.weight = weight;
    this.dist = 0;
  }
}

class BridgeQueue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
    this.weightSum = 0;
  }

  push(newNode) {
    if (this.tail) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.size += 1;
    this.weightSum += newNode.weight;
  }

  pop() {
    if (this.head) {
      let first = this.head;
      this.head = this.head.next;
      this.weightSum -= first.weight;
      this.size -= 1;
      if (this.size === 0) {
        this.tail = null;
      }
    } else {
      return undefined;
    }
  }

  move() {
    let now = this.head;
    while (now) {
      now.dist += 1;
      now = now.next;
    }
  }
}

const solution = (n, w, l, trucks) => {
  const bridge = new BridgeQueue();
  let answer = 0;
  let i = 0;
  while (i < n) {
    if (bridge.size > 0 && bridge.head.dist == w) {
      bridge.pop();
    }
    if (bridge.weightSum + trucks[i] <= l) {
      bridge.push(new TruckNode(trucks[i]));
      i++;
    }
    bridge.move();
    answer++;
  }

  while (bridge.size > 0) {
    if (bridge.head.dist === w) {
      bridge.pop();
    }
    bridge.move();
    answer++;
  }
  return answer;
};

console.log(solution(n, w, l, arr));

 

단방향 큐를 구현해서 문제를 해결했다. 단방향 큐 `BridgeQueue`가 다리를 나타내고, 그 큐에 사용되는 노드인 `TruckNode`가 다리 위에 올라간 트럭 하나하나를 나타낸다.

 

위 코드는 다음 과정을 반복하며 시뮬레이션한다.

1. 다리 끝에 도달한 트럭이 있으면 `BridgeQueue`에서 `pop`

2. 현재 다리에 올라간 트럭들의 무게 합과 다음에 올릴 트럭의 무게 합이 `l`을 넘지 않는다면 다음 순서 트럭을 다리에 올린다.

3. 모든 트럭을 한 칸씩 앞으로 전진한다.

4. 시간을 1 단위시간 증가시킨다.