[백준 / BOJ] 4949번 균형잡힌 세상 (Javascript / Node js)

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

단계별로 풀어보기도 어느새 스택 알고리즘에 도착했다. 이제 곧 재귀함수, 백트래킹, 조합 , 백트래킹 등 난이도 있는 문제들을 푸는날도 얼마 남지 않은 것 같다.

 

문제 해석

먼저 균형잡힌 문자열이 아닌 경우의 수들을 나눠보자.

 

1. 여는 괄호 '(' 또는 '[' 없이 닫는 괄호 ']' 또는 ')'가 있다면 균형잡힌 문자열이 아니다.
2. 닫는 괄호 바로 이전의 여는 괄호의 종류가 매칭되지 않으면 균형잡힌 문자열이 아니다.
3. 여는 괄호 '(' 또는 '[' 보다 닫는 괄호의 개수가 적으면 균형잡힌 문자열이 아니다.

 

---

 

 

위의 경우들을 통해 아래와 같은 알고리즘을 구상할 수 있다.

 

1. 먼저 문자열을 쪼개 배열에 담는다.

 

2. stack으로 사용할 배열을 담는다.

 

3. 문자열을 반복문을 통해 하나씩 검사하며 여는 종류의 괄호 '(' , '[' 가 나오면 push() 함수를 사용해 스택에 push한다.

 

4. 닫는 종류의 괄호 ')', ']'가 나오면 아래의 그림과 같이 해당 문자열의 종류에 따라 stack의 Top에 존재하는 여는 괄호의 종류를 검사한다. 만약 다른 종류의 여는 괄호가 Top에 존재한다면 "균형잡힌 문자열" 이 아니라는 결론을 내린다.

만약 종류가 같다면 pop() 함수를 통해 Top에 존재하는 값을 빼낸다.

 

5. 닫는 괄호가 나와서 stack의 Top을 검사했는데 비어있다면 마찬가지로 "균형잡힌 문자열" 이 아니라는 결론을 내린다.

 

6. 정상적으로 반복문이 끝난 뒤, stack에 아무것도 남아있지 않다면 "균형잡힌 문자열"이 맞다는 결론을 내린다.

 

 

전체코드

const fs = require("fs");

class main {
  constructor() {
    this.opend = "";
  }

  checkBalance(arr) {
    let balance = "";
    let stack = [];
    let str = "";
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === '(' || arr[i] === '[') {
        stack.push(arr[i]);
      }
      if (arr[i] === ")") {
        str = stack.pop();
        if (str !== "(") return "no";
      } else if (arr[i] === "]") {
        str = stack.pop();
        if (str !== "[") return "no";
      }
    }

    if (stack.length === 0) {
      balance = "yes";
    } else {
      balance = "no";
    }

    return balance;
  }

  solve() {
    const input = fs
      .readFileSync("../input.txt")
      .toString()
      .trim()
      .split("\n")
      .map((item) => item.split(''));

    input.pop();
   
    let answer = [];

    for (let i = 0; i < input.length; i++) {
      answer.push(this.checkBalance(input[i]));
    }

    console.log(answer.join('\n'));
  }
}

const app = new main();
app.solve();

 

코드는 우테코 프리코스 미션을 대비해서 일부러 백준 문제를 풀때도 객체 지향적으로 코드를 짜봤다.