자바스크립트로 알고리즘 정리하기 #5 Stack 연습문제2

자바스크립트로 알고리즘 정리하기 #5 Stack 연습문제2

Boj 1918 후위표기식 (어려움)

문제 링크

Stack을 연습하기 좋은 문제 같다.

위 문제는 쉬워보이지만 막상 풀려면 상당히 어려운 문제이다. 일반적으로는 자료구조 시간에 책을 보고 코드를 한번쯤 따라치게 된다.

문제풀이의 핵심은 다음 규칙을 잘 따르는 것이다.

1. 알파벳이 나오는 경우에는 무조건 그냥 출력한다.

• 나의 경우에는 answer라는 문자열에 그냥 더해주었다.

2. 연산자가 나오면서 다음 조건에 충족하면 스택에 넣는다.

• 스택이 비어있다.
• stack.top()이 (이다.
• stack.top()에 존재하는 연산자 우선순위보다 지금 들어온 연산자 우선순위가 더 크다.

3. 위의 경우가 아니라면, 위의 경우를 충족하거나 스택이 빌 때까지 stack.top()을 pop()하여 출력하고, 들어온 연산자는 마지막에 스택에 push()한다.
4. ( 열린 괄호가 들어온다면, 일단 스택에 넣는다.
5. ) 닫힌 괄호가 들어온다면, (열린 괄호가 나오거나 스택이 빌 때까지 스택을 pop()한 것을 출력한다. ((열린 괄호는 출력하지 않는다.)
6. 마지막으로 스택에 남은 것들 전부 pop()연산으로 출력해준다.

결과 코드

let solution = (line) => {
  let operatorMap = {'/': 2, '*': 2, '+': 1, '-': 1};
  let operators = Object.keys(operatorMap);
  let equationStack = line.split('').reverse();
  let stack = [];
  let answer = '';

  while (equationStack.length !== 0) {
    let token = equationStack.pop();

    // if token is a one of operators
    if (operators.includes(token)) {
      if (
        stack.length === 0 || // When stack is empty
        stack[stack.length - 1]  === '(' || // When stack top is '('
        operatorMap[stack[stack.length - 1]] < operatorMap[token] // When Token's precedence is higher than stack top
      ) {
        stack.push(token);
        continue;
      }

      while (
        !(
          stack.length === 0 ||
          stack[stack.length - 1] === '(' ||
          operatorMap[stack[stack.length - 1]] < operatorMap[token]
        )
      ) {
        answer += stack.pop();
      }

      stack.push(token);
      continue;
    }

    if (token === ')') {
      while (stack.length !== 0 && stack[stack.length - 1] !== '(') {
        answer += stack.pop();
      }

      if (stack.length !== 0) {
        stack.pop();
      }

      continue;
    }

    if (token === '(') {
      stack.push(token);
      continue;
    }

    answer += token;
  }

  while (stack.length !== 0) {
    answer += stack.pop();
  }

  return answer;
};

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

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

Boj 10808 알파벳 개수

문제 링크

알파벳의 개수를 세는 문제인데 사실 스택을 사용하지 않아도 된다. 근데 사용해도 된다.

let solution = (line) => {
  let answer = Array(26).fill(0);

  line.split('').map((e) => {
    answer[e.charCodeAt(0) - 97] += 1;
  });

  return answer.join(' ');
};

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

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

Boj 10820 문자열 분석

문제 링크

정규표현식을 이용하여 쉽게 풀 수 있다.

스택은 써도되고 안써도 되는 것 같다.

let solution = (input) =>
  input
    .map((line) =>
      ['[a-z]', '[A-Z]', '[0-9]', ' ']
        .map((reg) => {
          let matches = line.match(RegExp(reg, 'g'));
          return matches ? matches.length : 0;
        })
        .join(' ')
    )
    .join('\n');

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(solution(input));
  process.exit();
});