자바스크립트로 알고리즘 정리하기 #1 백준 nodejs 표준 입출력 + 스택 및 관련 문제 풀이

Jake Seo·2020년 8월 14일
3

javascript-algorithm

목록 보기
1/11

자바스크립트로 알고리즘 정리하기 #1 백준 nodejs 표준 입출력 + 스택 및 관련 문제 풀이

백준 Node.js 입출력

백준의 node.js에서는 속도를 위해 주로 다음과 같은 입출력을 사용한다.

(function () {
  let inputLines = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .split("\n");
})();

이는 node.js의 fs.readFileSync() 메소드를 이용한 방법이다.

동기방식으로 파일을 읽어와 'path 파라미터의 내용을 반환한다.' 고 나와있다.

리눅스의 dev에는 여러가지가 있는데,

/dev/tty는 현재 프로세스를 제어하는 터미널이다. 인터럽트 문자를 타이프하거나 작업제어를 수행하면 이를 이해하는 터미널이다.
/dev/stdin은 표준 입력장치이다. 콘솔 키보드 드라이버에서 값을 읽어와 입력을 받고 처리할 수 있게 해준다.
/dev/stdout은 표준 출력장치이다. 콘솔 모니터 드라이버를 이용해 모니터에 출력한다.
/dev/stderr은 표준 에러장치이다.

이 중 /dev/stdin을 이용해 입력을 받아서 입출력을 하는 것이다.

아래와 같은 방법으로도 입출력이 가능하다.

const readLine = require("readline");

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

rl.on("line", function(line) {
	console.log("hello !", line);
  	rl.close();
}).on("close", function() {
	process.exit();
})

여러 줄을 받고 싶다면?

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

let input = [];

rl.on('line', function (line) {
    input.push(line)
  })
  .on('close', function () {
    console.log(input);
    process.exit();
});

스택이란?

  • 한쪽 끝에서만 자료를 넣고 뺄 수 있는 구조

  • push() : 넣을 때 가장 위의 데이터로 들어간다.
  • pop() : 뺄 때 가장 위의 데이터가 빠진다

자바스크립트 스택 구현

  1. push() : 스택에 엘리먼트 추가
  2. pop() : 스택 맨 위의 엘리먼트 삭제하며 반환
  3. peek() : 스택 맨 위의 엘리먼트를 반환
  4. length() : 스택의 엘리먼트의 총 갯수를 반환
  5. search() : 스택의 엘리먼트를 검색
  6. isEmpty() : 스택이 비었는지 확인
  7. print() : 스택의 엘리먼트들을 출력
  8. reverse() : 스택의 원소들을 거꾸로 출력
class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0;
  }

  pop() {
    if (this.isEmpty() === false) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}

참고

boj 10828

문제 링크

스택을 구현하고 들어온 문자열에 따라 스택 연산을 처리한 뒤에 결과를 출력하면 된다.

boj에서 node.js를 써서 문제를 푸는게 어색해서 node.js의 입출력 방식 때문에 약간 고생을 했다.

한줄씩 출력하라고해서 한줄씩 출력했더니 시간초과가 떴다. 이런..

문자열 변수 하나에 저장해두었다가 한 번에 출력하니 시간초과가 뜨지 않았다.

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  _top() {
    if (!this.isEmpty()) {
      return this.data[this.top - 1];
    }

    return -1;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0 ? 1 : 0;
  }

  pop() {
    if (!this.isEmpty()) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }

    return -1;
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}

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

let stack = new Stack();
let answer = '';

const stackCLI = (line) => {
  let [command, element] = line.split(' ');

  if (command === 'push') {
    stack.push(+element);
  } else if (command === 'pop') {
    answer += stack.pop() + '\n';
  } else if (command === 'top') {
    answer += stack._top() + '\n';
  } else if (command === 'size') {
    answer += stack.length() + '\n';
  } else if (command === 'empty') {
    answer += stack.isEmpty() + '\n';
  }
};

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {
  input.map((line) => {
    stackCLI(line);
  });

  console.log(answer);
  process.exit();
});

boj 9093

문제 링크

스택에 무언가 넣었다가 뺄 때는 거꾸로 나온다는 성질을 이용한 문제이다.

사실 그냥 배열의 메소드 중에 reverse()를 사용하면 제일 간단하게 풀 수 있다.

근데 스택이 지금의 주제니까 그냥 스택으로 풀어보았다.

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  _top() {
    if (!this.isEmpty()) {
      return this.data[this.top - 1];
    }

    return -1;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0 ? 1 : 0;
  }

  pop() {
    if (!this.isEmpty()) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }

    return -1;
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}

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

let stack = new Stack();
let answer = '';

const reverseSentence = (line) => {
  let tokens = line.split(' ');

  answer +=
    tokens
      .map((token) => {
        let reversed = [];

        token.split('').map((alphabet) => {
          stack.push(alphabet);
        });

        while (!stack.isEmpty()) {
          reversed.push(stack.pop());
        }

        return reversed.join('');
      })
      .join(' ') + '\n';
};

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {
  input.splice(0, 1);

  input.map((line) => {
    reverseSentence(line);
  });

  console.log(answer);
  process.exit();
});

boj 9012

문제 링크

이 문제에서 핵심은 여는 괄호랑 닫는 괄호랑 짝이 맞느냐이다.

나의 생각엔 닫는 괄호만 신경쓰면 된다고 생각했는데,

  • 닫는 괄호())가 나왔을 때
    1. 스택의 맨 위에 여는 괄호(()가 있는지 보고 만약에 없다면 짝이 안맞는 것이니 "NO"를 반환한다.
    • 닫는 괄호만 나온 케이스
    1. 스택의 맨 위에 여는 괄호(()가 있다면, pop()을 하여 없애준다.
    • 정상 케이스
    1. 마지막에 짝이 다 맞아서 스택에 아무것도 없다면 "YES"를 반환한다.
    • 정상 케이스
    1. 스택에 무언가 남아있다면 "NO"를 반환한다.
    • 여는 괄호가 남은 케이스
class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0;
  }

  pop() {
    if (this.isEmpty() === false) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}

let answer = "";

let solution = (str) => {
  let stack = new Stack();

  for (let i = 0; i < str.length; i++) {
    let thisChar = str[i];

    if (thisChar === "(") {
      stack.push(thisChar);
    }

    if (thisChar === ")") {
      if (stack.pop() !== "(") {
        return "NO";
      }
    }
  }

  if (!stack.isEmpty()) {
    return "NO";
  }

  return "YES";
};

(function () {
  /*
  test cases in boj

  let exampleCase1 =
    "6\n(())())\n(((()())()\n(()())((()))\n((()()(()))(((())))()\n()()()()(()()())()\n(()((())()(";

  console.log(exampleCase1);
  exampleCase1
    .split("\n")
    .slice(1)
    .map((e) => {
      solution(e);
    });

  let exampleCase2 = "3\n((\n))\n())(()";

  exampleCase2
    .split("\n")
    .slice(1)
    .map((e) => {
      solution(e);
    });
    */

  let inputLines = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .split("\n")
    .slice(1, -1);

  console.log(inputLines.map((input) => solution(input)).join("\n"));
})();

boj 1874

문제 링크

이 문제의 경우에는 cnt라는 기준 수가 있고, 이 수는 오름차 순으로 증가한다.
1. 입력으로 이 수보다 큰 수가 들어왔을 때는 cnt를 증가시키며 스택에 값을 채운다.
2. 입력으로 들어온 수가 pop() 했을 때 나올 수 있는 수라면 pop()을 하고 -를 정답에 채운다.
3. 입력으로 들어온 수가 cnt보다 작으면서 pop()했을 때 나올 수 없다면 "NO"를 반환한다.

처음에 N을 따로 지정해주지 않고 inputLines.length를 이용해서 풀었는데, 그 경우에 마지막 테스트케이스에 대해 틀렸다고 나온다. 그 이유는 아마 \n\n과 같이 쓸데없는 공백 라인이 있는 테스트케이스가 존재해서 그런 것 같다.

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0;
  }

  pop() {
    if (this.isEmpty() === false) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}

let answer = "";

let solution = (inputLines) => {
  /**
   * 처음에 N을 따로 지정해주지 않고 inputLines.length를 이용해서
   * 풀었는데, 그 경우에 마지막 테스트케이스에 대해 틀렸다고 나온다.
   * 그 이유는 아마 \n\n과 같이 쓸데없는 공백 라인이 있는
   * 테스트케이스가 존재해서 그런 것 같다.
   */
  let N = inputLines.splice(0, 1)[0];
  let cnt = 0;
  let stack = new Stack();
  for (let i = 0; i < N; i++) {
    cur = +inputLines[i];
    while (cur > cnt) {
      stack.push(++cnt);
      answer += "+\n";
    }

    if (stack.pop() !== cur) {
      return "NO";
    }

    answer += "-\n";
  }

  return answer;
};

(function () {
  let inputLines = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .split("\n");

  console.log(solution(inputLines));
})();

boj 1406

문제 링크

이 문제의 경우 커서가 left 스택과 right 스택 사이에 있다고 생각하면 쉽다.

  • 커서를 왼쪽으로 움직이면 문자열이 left에서 right으로 넘어간다.
  • 커서를 오른쪽으로 움직이면 문자열이 right에서 left로 넘어간다.
  • 단, 마지막 출력에서는 기존에 왼쪽에서 오른쪽으로 보는 기준으로 문자열을 출력하기 때문에, right 스택에 있는 데이터는 거꾸로 출력해주어야 한다. (순서대로 pop() 메소드를 수행한 결과를 반환하면 거꾸로 나온다.)

스택을 활용할 때 어떠한 기준점을 갖고 두 값들 사이에 위치할 수 있다는 개념을 알면 될 것 같다. 매번 처음부터 해당 기준까지 커서를 옮긴다고 가정하면 너무나 많은 시간복잡도가 걸린다.

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0;
  }

  pop() {
    if (this.isEmpty() === false) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}
let left = new Stack();
let right = new Stack();
let answer = "";

let solution = (inputLines) => {
  inputLines
    .shift()
    .split("")
    .map((c) => {
      left.push(c);
    });

  let n = inputLines.shift();

  for (let i = 0; i < n; i++) {
    let command = inputLines[i].split(" ")[0];

    if (command === "L") {
      if (!left.isEmpty()) {
        right.push(left.pop());
      }
    }

    if (command === "D") {
      if (!right.isEmpty()) {
        left.push(right.pop());
      }
    }

    if (command === "B") {
      if (!left.isEmpty()) {
        left.pop();
      }
    }

    if (command === "P") {
      let arg = inputLines[i].split(" ")[1];
      left.push(arg);
    }
  }

  answer += left.data.join("");
  answer += right.data.reverse().join("");

  return answer;
};

(function () {
  let inputLines = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .split("\n");

  console.log(solution(inputLines));
})();

스택의 문제풀이 핵심 개념

LIFO(Last In First Out)
마지막에 온 값부터 의미를 갖는다면 스택 사용 가능.

profile
Jake Seo
풀스택 웹개발자로 일하고 있는 Jake Seo입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. 프론트엔드: Javascript, React 백엔드: Spring Framework에 관심이 있습니다.
다음 포스트

자바스크립트로 알고리즘 정리하기 #2 Queue 구현 및 관련 문제풀이

0개의 댓글