[백준 23309] 철도 공사 (자바스크립트)

문제

연세대학교가 위치한 신촌역이 속한 2호선은 그림과 같이 N개의 역이 원형으로 연결되어 있다. 각 역은 고유 번호가 할당돼 있으며 역들의 고유 번호는 서로 다르다. 그리고 특정 역의 다음 역은 시계 방향으로 인접한 역을 의미하고, 이전 역은 반시계 방향으로 인접한 역을 의미한다.

2호선은 지하철 노선들 중 유일한 흑자 노선이다. 때문에 2호선 공사 자금이 넉넉하기에 M번의 공사를 거치려고 한다. 각 공사는 다음 4가지 중 하나를 시행한다.

• 고유 번호 i를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j인 역을 설립한다.
• 고유 번호 i를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j인 역을 설립한다.
• 고유 번호 i를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
• 고유 번호 i를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.

이 때, 이미 설립한 역은 다시 설립하지 않으며 폐쇄한 역은 다시 설립될 수 있다. 그리고 폐쇄 작업은 현재 설립된 역이 2$2$개 이상일 때만 들어온다.

2호선을 공사하는 프로그램을 만들어보자.

입력

첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 N과 공사 횟수를 나타내는 양의 정수 M이 주어진다. (1 ≤ N ≤ 500,000, 1≤ M ≤ 1,500,000)

두 번째 줄에는 공사를 시작하기 이전에 있는 역의 고유 번호를 시계 방향 순서대로 주어진다. 같은 고유 번호를 가진 역은 주어지지 않는다.

이후 M개의 줄에 걸쳐서 공사에 대한 정보를 다음과 같이 주어진다.

• BN i j : 고유 번호 i를 가진 역의 다음 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j인 역을 설립한다.
• BP i j : 고유 번호 i를 가진 역의 이전 역의 고유 번호를 출력하고, 그 사이에 고유 번호 j인 역을 설립한다.
• CN i : 고유 번호 i를 가진 역의 다음 역을 폐쇄하고 그 역의 고유 번호를 출력한다.
• CP i : 고유 번호 i를 가진 역의 이전 역을 폐쇄하고 그 역의 고유 번호를 출력한다.

입력으로 들어오는 모든 역의 고유 번호는 1 이상 1,000,000 이하의 양의 정수다. 폐쇄 작업은 현재 설립된 역이 2개 이상일 때만 들어오며, 이미 설립된 역은 또 설립될 수 없지만 폐쇄된 역은 다시 설립될 수 있다.

출력

각 공사에 대한 출력 값을 M개의 줄에 걸쳐서 출력한다.

---

#풀이과정

문제 자체는 원형 연결 리스트로 풀 수 있다.

진짜 문제는 시간 초과 난다는 것...

시간 초과를 어떻게 해결해야 할지 몰라서.. 일단 완성한 코드..

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

class Node {
  constructor(id) {
    this.id = id;
    this.next = null;
    this.prev = null;
  }
}

class CircularLinkedList {
  constructor() {
    this.nodes = new Map();
    this.head = null;
  }

  init(id) {
    if (id.length === 0) return;

    // 첫 번째 값을 헤드로 지정
    let prevNode = new Node(id[0]);
    this.head = prevNode;
    this.nodes.set(id[0], prevNode);

    const firstNode = prevNode;

    // 원형 리스트 생성
    for (let i = 1; i < id.length; i++) {
      let newNode = new Node(id[i]);
      prevNode.next = newNode;
      newNode.prev = prevNode;
      this.nodes.set(id[i], newNode);
      prevNode = newNode;
    }
    
    // 마지막 노드와 첫 번째 노드 연결
    prevNode.next = firstNode;
    firstNode.prev = prevNode;
  }

  // BN i j : 고유 번호 i를 가진 역의 다음 역의 번호를 출력 후, 그 사이에 고유 번호 j의 역을 삽입
  BN(i, j) {
    const current = this.nodes.get(i);
    const nextNode = current.next;
    const output = nextNode.id;
    const newNode = new Node(j);

    // 새로운 노드를 current와 nextNode 사이에 삽입
    current.next = newNode;
    newNode.prev = current;
    newNode.next = nextNode;
    nextNode.prev = newNode;

    // 새로운 역 추가
    this.nodes.set(j, newNode);
    return output;
  }

  // BP i j : 고유 번호 i를 가진 역의 이전 역의 번호를 출력 후, 그 사이에 고유 번호 j의 역을 삽입
  BP(i, j) {
    const current = this.nodes.get(i);
    const prevNode = current.prev;
    const output = prevNode.id;
    const newNode = new Node(j);

    // 새로운 노드를 prevNode와 current 사이에 삽입
    prevNode.next = newNode;
    newNode.prev = prevNode;
    newNode.next = current;
    current.prev = newNode;

    // 새로운 역 추가
    this.nodes.set(j, newNode);
    return output;
  }

  // CN i : 고유 번호 i를 가진 역의 다음 역을 폐쇄(삭제)하고, 그 역의 번호를 출력
  CN(i) {
    const current = this.nodes.get(i);
    const removeNode = current.next;
    const output = removeNode.id;
    const afterRemove = removeNode.next;

    // current와 afterRemove를 연결하여 removeNode를 리스트에서 제외
    current.next = afterRemove;
    afterRemove.prev = current;

    // 폐쇄된 역 제거
    this.nodes.delete(removeNode.id);
    return output;
  }

  // CP i : 고유 번호 i를 가진 역의 이전 역을 폐쇄(삭제)하고, 그 역의 번호를 출력
  CP(i) {
    const current = this.nodes.get(i);
    const removeNode = current.prev;
    const output = removeNode.id;
    const beforeRemove = removeNode.prev;

    // beforeRemove와 current을 연결하여 removeNode를 리스트에서 제외
    current.prev = beforeRemove;
    beforeRemove.next = current;

    // 폐쇄된 역 제거
    this.nodes.delete(removeNode.id);
    return output;
  }
}

const [N, M] = input[0].split(" ").map(Number);
const initialStations = input[1].split(" ").map(Number);

const list = new CircularLinkedList();
list.init(initialStations);

const outputLines = [];

for (let i = 2; i < 2 + M; i++) {
  const parts = input[i].split(" ");
  const command = parts[0];

  if (command === "BN") {
    const station = Number(parts[1]);
    const newStation = Number(parts[2]);
    const res = list.BN(station, newStation);
    outputLines.push(res);
  } else if (command === "BP") {
    const station = Number(parts[1]);
    const newStation = Number(parts[2]);
    const res = list.BP(station, newStation);
    outputLines.push(res);
  } else if (command === "CN") {
    const station = Number(parts[1]);
    const res = list.CN(station);
    outputLines.push(res);
  } else if (command === "CP") {
    const station = Number(parts[1]);
    const res = list.CP(station);
    outputLines.push(res);
  }
}

console.log(outputLines.join("\n"));