[백준] 9012번: 괄호 (Node.js)

 

접근방식

자료형 구조인(stack)을 사용하여, 문제를 해결하는데에 초점을 둔 문제인 것 같습니다.

 

스택은 선형 자료구조로 데이터가 차례로 쌓이면서 순서가 유지되며, 후입선출 방식으로 작동하는 자료구조입니다.

아래 이미지를 참조하면 쉽게 이해하실 수 있습니다.

img출처: https://www.programiz.com/dsa/stack

 

빈 스택에 1, 2, 3을 차례대로 넣을 때는 1이 맨밑 그다음 2, 3 순으로 들어갑니다.

하지만 나올 때는 먼저 들어간 1이 아닌 맨 나중에 들어간 3, 2, 1순으로 나오는 자료구조입니다.

 

 

풀이 ⏰

이와 같이 stack 자료구조를 사용해보면,

"(" 를 만나면 stack에 넣고(push) , ")" 를 만나면 stack에서 "("를 빼면 됩니다(pop).

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 () {
  for (let i = 1; i < input.length; i++) {
    let stack = [];
    let item = input[i].split("");
    let result = true;
    for (let j = 0; j < item.length; j++) {
      // "(" 를 만나면 stack에서 push
      if (item[j] === "(") {
        stack.push(item[j]);
        // ")" 를 만나면 stack에서 pop
        // stack이 빈배열인 상태에서 ")"를 만나면 for문을 빠져나가기
      } else {
        if (!stack.pop()) {
          result = false;
          break;
        }
      }
    }
    // stack이 빈배열이 아니라면 ex) ["("] 하나라도 남은것
    if (stack.length !== 0) {
      result = false;
    }

    if (result) {
      console.log("YES");
    } else {
      console.log("NO");
    }
  }
});

 

 

다른 방법으로는 "()"  한 쌍이 이루어지면 제거하는 방식으로 푸는 방법입니다.

예를 들어 "((()))"가 있을 떄, "()"를 빈값으로 만들면 "(())"가 나옵니다.

do...while문을 통해 해당 작업을 반복하였습니다.

 

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 () {
  for (let i = 1; i < input.length; i++) {
    let item = input[i];
    let find = "()";
    // 정규식을 이용하여 "()"를 빈 값으로 만듭니다.
    // ex) ((())) => (())
    do {
      item = item.replace(/\(\)/g, "");
    } 
    // 만약 아직도 "()"가 포함되어 있으면 do while문 실행
    while (item.includes(find));
    if (item == "") {
      console.log("YES");
    } else {
      console.log("NO");
    }
  }
});

 

 

백준 9012번 링크

👉 https://www.acmicpc.net/problem/9012