[Javascript/자바스크립트, Python/파이썬] 백준 15828번 Router

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

파이썬 코드(100점)

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
q = deque()

while True:
    input_data = int(input())
    if input_data == -1:
        break
    if input_data == 0:
        q.popleft()
        continue
    if len(q) >= n:
        continue
    else:
        q.append(input_data)

if len(q) > 0:
    print(" ".join(list(map(str, q))))
else:
    print("empty")

 

파이썬에는 양방향 큐 자료구조인 deque가 내장 라이브러리에 있기 때문에 이 deque를 이용해서 쉽게 풀이할 수 있다.

다만 주의해야할 점은 입출력에 필요한 시간을 최대한 줄여야 한다는 것이다. 위 코드에서는 2가지 방법으로 입출력 시간을 줄였다.

 

1. `input` 대신 `sys.stdin.readline` 사용

`input`은 다음과 같은 이유로 `sys.stdin.readline`보다 느리다.

- `input`은 인자로 prompt message를 출력할 수 있음

- `input`은 개행 문자를 삭제한 값을 리턴한다.

그렇기 때문에 위와 같은 작업이 필요없고, 빠른 연산이 필요할 때에는 `sys.stdin.readline`을 사용하여 작업 속도를 빠르게 할 수 있다.

 

2. q에 남은 원소들을 출력할 때 하나의 문자열로 만들어서 출력

많은 입출력은 코테 문제를 풀 때 시간 초과의 원인일 때가 많다. 그렇기 때문에 어떻게 하든 입출력 작업은 최대한 줄이는 것이 좋다.

여기서는 q에 있는 원소 하나마다 `print`하는 방식으로 출력할 수도 있지만, `print`의 호출 횟수를 줄이기 위해 join을 사용하여 하나의 문자열로 만들고, 해당 문자열을 한 번만 출력하는 형식으로 시간을 줄였다.

자바스크립트 코드(100점)

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

  setNext(node) {
    this.next = node;
  }
}

class Queue {
  constructor(maxSize) {
    this.size = 0;
    this.head = null;
    this.tail = null;
    this.maxSize = maxSize;
  }

  push(value) {
    if (this.size >= this.maxSize) return;

    const newNode = new Node(value);
    if (this.head) {
      this.tail.setNext(newNode);
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.size++;
  }

  pop() {
    this.head = this.head.next;
    this.size--;
  }
}

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
const [n, ...input_data] = fs
  .readFileSync(filePath)
  .toString()
  .split("\n")
  .map((num) => +num);

const q = new Queue(n);
let idx = 0;

while (1) {
  if (input_data[idx] === -1) break;
  else if (input_data[idx] === 0) q.pop();
  else q.push(input_data[idx]);
  idx++;
}

if (q.size === 0) console.log("empty");
else {
  const answer = [];
  let now = q.head;
  for (let j = 0; j < q.size; j++) {
    answer.push(now.value);
    now = now.next;
  }
  console.log(answer.join(" "));
}

 

자바스크립트에는 양방향 큐가 없기 때문에 연결리스트 형태로 FIFO가 가능한 자료구조를 정의해서 사용했다.