자바스크립트로 알고리즘 정리하기 #1 백준 nodejs 표준 입출력 + 스택 및 관련 문제 풀이
백준의 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()
: 뺄 때 가장 위의 데이터가 빠진다push()
: 스택에 엘리먼트 추가pop()
: 스택 맨 위의 엘리먼트 삭제하며 반환peek()
: 스택 맨 위의 엘리먼트를 반환length()
: 스택의 엘리먼트의 총 갯수를 반환search()
: 스택의 엘리먼트를 검색isEmpty()
: 스택이 비었는지 확인print()
: 스택의 엘리먼트들을 출력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에서 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();
});
스택에 무언가 넣었다가 뺄 때는 거꾸로 나온다는 성질을 이용한 문제이다.
사실 그냥 배열의 메소드 중에 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();
});
이 문제에서 핵심은 여는 괄호랑 닫는 괄호랑 짝이 맞느냐이다.
나의 생각엔 닫는 괄호만 신경쓰면 된다고 생각했는데,
)
)가 나왔을 때(
)가 있는지 보고 만약에 없다면 짝이 안맞는 것이니 "NO"
를 반환한다.(
)가 있다면, pop()
을 하여 없애준다."YES"
를 반환한다."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"));
})();
이 문제의 경우에는 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));
})();
이 문제의 경우 커서가 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)
마지막에 온 값부터 의미를 갖는다면 스택 사용 가능.