스택


10828번 (스택)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
const stack = [];
const answer = [];
for (let i = 1; i <= input[0]; i++) {
if (input[i].includes('push')) {
stack.push(input[i].split(' ')[1]);
} else if (input[i] === 'pop') {
if (stack.length === 0) {
answer.push(-1);
} else {
answer.push(stack.pop());
}
} else if (input[i] === 'size') {
answer.push(stack.length);
} else if (input[i] === 'empty') {
if (stack.length === 0) {
answer.push(1);
} else {
answer.push(0);
}
} else if (input[i] === 'top') {
if (stack.length === 0) {
answer.push(-1);
} else {
answer.push(stack[stack.length - 1]);
}
}
}
console.log(answer.join('\n'));
  • 스택에 대해 자료구조만 이해하고 있다면 풀 수 있는 문제였다.
  • 여러 방법이 있지만 스택과 정답 배열을 만들어두고 정답배열에 push하며 진행하는 간단한 방법으로 해결했다.
  • 10773번 (제로)

    const fs = require('fs');
    const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
    const K = +input.shift();
    const stack = [];
    let answer = 0;
    for (let i = 0; i < K; i++) {
    if (input[i] !== '0') {
    stack.push(input[i]);
    } else {
    stack.pop();
    }
    }
    for (let i = 0; i < stack.length; i++) {
    answer += +stack[i];
    }
    console.log(answer);
  • 스택을 하나 만들고 마지막에 안에 있는 숫자들을 모두 answer 변수에 담아주었다.
  • 9012번 (괄호)

    const fs = require('fs');
    const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
    const T = +input.shift();
    const answer = new Array(T).fill(null);
    let stack = 0;
    for (let i = 0; i < T; i++) {
    stack = 0;
    const str = input[i].split('');
    for (let j = 0; j < str.length; j++) {
    if (str[j] === '(') {
    stack += 1;
    } else if (str[j] === ')' && stack === 0) {
    answer[i] = 'NO';
    } else {
    stack -= 1;
    }
    }
    if (stack === 0 && answer[i] === null) {
    answer[i] = 'YES';
    } else {
    answer[i] = 'NO';
    }
    }
    console.log(answer.join('\n'));
  • 스택이 꼭 배열일 필요는 없었다. 여는 괄호라면 +1을 해주고 닫는 괄호라면 -1을 해주었다.
  • 닫는괄호가 등장했는데 스택이 0이면 이미 NO 이므로 NO를 넣어주었다.
  • 안쪽 for문이 종료되고 만약 stack이 0이고 NO가 들어가있지 않은 상태면 YES를 넣어주었다.
  • 나머지는 스택이 1이 아닌 것으므로 NO를 넣어주었다.
  • 4949번 (균형잡인 세상)

    const fs = require('fs');
    const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n');
    const filteredInput = input.filter(el => el !== '.');
    const answer = new Array(filteredInput.length).fill(null);
    let stack = [];
    for (let i = 0; i < answer.length; i++) {
    stack = [];
    const str = filteredInput[i].split('');
    str.pop();
    for (let j = 0; j < str.length; j++) {
    if (str[j] === '[') {
    stack.push('[');
    } else if (str[j] === '(') {
    stack.push('(');
    } else if (str[j] === ']') {
    if (stack.length === 0) {
    answer[i] = 'no';
    break;
    }
    if (stack[stack.length - 1] === '[') {
    stack.pop();
    } else {
    answer[i] = 'no';
    break;
    }
    } else if (str[j] === ')') {
    if (stack.length === 0) {
    answer[i] = 'no';
    break;
    }
    if (stack[stack.length - 1] === '(') {
    stack.pop();
    } else {
    answer[i] = 'no';
    break;
    }
    }
    }
    if (answer[i] === null) {
    if (stack.length === 0) {
    answer[i] = 'yes';
    } else {
    answer[i] = 'no';
    }
    }
    }
    console.log(answer.join('\n'));
  • 풀리긴 했지만 하드코딩으로 푼 것 같아 마음이 불편했다. 오랜만에 코테를 풀어서인가 더 좋은 해결법이 나오질 못했다.
  • 우선 . 만 있는 문자열은 filter로 걸러냈다.
  • stack을 만들고 여는 괄호는 추가해주면서, 해당 stack의 마지막 요소가 지금 등장한 닫는 괄호와 맞을 때에만 pop을 해주었다.
  • 외의 예외들은 모두 no를 넣어주고 break했다.
  • stack의 길이가 0인 경우 yes, 아닌 경우 no를 넣어줬다.
  • 1874번 (스택 수열)

    const fs = require('fs');
    const input = fs.readFileSync('./dev/stdin').toString().trim().split('\n').map(Number);
    const n = +input.shift();
    const stack = [];
    let answer = '';
    let count = 1;
    let i = 0;
    while (true) {
    if (i === n) break;
    if (count <= input[i]) {
    stack.push(count);
    count++;
    answer += '+\n';
    } else {
    if (stack[stack.length - 1] !== input[i]) {
    answer = 'NO';
    break;
    }
    stack.pop();
    i++;
    answer += '-\n';
    }
    }
    console.log(answer.trim());
  • count는 스택에 push할 다음 숫자이다.
  • input의 i번째 숫자보다 count가 더 커질때까지 count를 1씩 증가시키고, 스택에 push를 한다. 정답에는 +를 추가한다.
  • count가 input의 i번째 숫자보다 커지면, count를 pop하고 i를 1 증가시켜 다음 숫자를 가리키게 한다. 정답에는 -를 추가한다.
  • i가 n과 같아지면 while문을 탈출한다.
  • answer를 출력한다.