백준 10828 스택

자료구조를 바탕으로 백준에 있는 스택 문제를 풀어보았다.

자료구조를 공부할 때 작성한 코드보다 확실히 조금 더 방어코드가 필요했다.

문제 : https://www.acmicpc.net/problem/10828

문제에서 친절하게 제한 사항들을 설명해주기 때문에 그대로 구현하면 된다. 나는 그래도 최대한 성능상 효율을 내기 위해서 링크드 리스트로 스택을 구현해보았다.

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = input.splice(0, 1);

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

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(value) {
    const newNode = new Node(value);
    if (this.top === null) {
      this.top = newNode;
      this.top.next = newNode;
      this.size += 1;
    } else {
      newNode.next = this.top;
      this.top = newNode;
      this.size += 1;
    }
  }

  pop() {
    if (this.size === 0) {
      return -1;
    } else {
      const value = this.top.value;
      this.top = this.top.next;
      this.size -= 1;
      return value;
    }
  }

  getSize() {
    return this.size;
  }

  empty() {
    if (this.size === 0) return 1;
    else return 0;
  }

  getTop() {
    if (this.size === 0) {
      return -1;
    } else return this.top.value;
  }
}

const myStack = new Stack();
for (let i = 0; i < input.length; i++) {
  if (input[i] === 'top') {
    console.log(myStack.getTop());
  } else if (input[i] === 'size') {
    console.log(myStack.getSize());
  } else if (input[i] === 'empty') {
    console.log(myStack.empty());
  } else if (input[i] === 'pop') {
    console.log(myStack.pop());
  } else {
    const [command, value] = input[i].split(' ');
    myStack.push(Number(value));
  }
}

Node.js 백준의 특성상 입력받는 코드가 길어질 수 밖에 없다...ㅠㅠ 좀 고쳐주세요

그런데 결과는 시간초과!

왜일까 한참을 생각했다. 아무리 생각해도 출력도 잘되고 엣지케이스도 없는거 같은데 심지어 성능때문에 링크드리스트로 작성했는데도 안된다? 그냥 자바스크립트가 구린건가? 자스로는 백준 못푸나? 이런생각했다 😥

문제는console.log에 있었다.

콘솔로그는 원래 디버깅용 함수이기 때문에 속도가 느리다는 말이었다. 자세한건 스택오버플로우 링크에서 참고해보자!
https://stackoverflow.com/questions/2934509/exclude-debug-javascript-code-during-minification

그래서 결론적으로 answer라는 빈문자열에 정답들을 모두 담아서 마지막에 한번만 출력해줬더니 정답처리되었다.

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = input.splice(0, 1);

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

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push(value) {
    const newNode = new Node(value);
    if (this.top === null) {
      this.top = newNode;
      this.top.next = newNode;
      this.size += 1;
    } else {
      newNode.next = this.top;
      this.top = newNode;
      this.size += 1;
    }
  }

  pop() {
    if (this.size === 0) {
      return -1;
    } else {
      const value = this.top.value;
      this.top = this.top.next;
      this.size -= 1;
      return value;
    }
  }

  getSize() {
    return this.size;
  }

  empty() {
    if (this.size === 0) return 1;
    else return 0;
  }

  getTop() {
    if (this.size === 0) {
      return -1;
    } else return this.top.value;
  }
}

const myStack = new Stack();
let answer = '';
for (let i = 0; i < input.length; i++) {
  if (input[i] === 'top') {
    answer += myStack.getTop() + '\n';
  } else if (input[i] === 'size') {
    answer += myStack.getSize() + '\n';
  } else if (input[i] === 'empty') {
    answer += myStack.empty() + '\n';
  } else if (input[i] === 'pop') {
    answer += myStack.pop() + '\n';
  } else {
    const [command, value] = input[i].split(' ');
    myStack.push(Number(value));
  }
}
console.log(answer);