baekjoon. 괄호

문제

문제 링크

9012번: 괄호

풀이

스택을 이용해서 풀면 될 것 같았다

문자열의 앞부분 부터 하나씩 스택에 넣으면서(push) 괄호가 유효한 쌍이 되면 그 쌍을 빼버리고(pop) 문자열이 끝났을 때 스택이 비어있게된다면 그 문자열은 VPS가 된다

VPS가 되지 않는 경우를 생각해보면

• 스택에 닫는 괄호 ')'가 남아있으면 그 문자열은 vps가 될 수 없다
• 문자열을 다 돌았을 때 스택에 문자가 남아있으면 그 문자열은 vps가 될 수 없다

 

두 가지만 생각하면 될 것 같다

코드

   const input = `6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(`.split('\n').slice(1);

    // const input = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n').slice(1);


    let  answer = '';
    for(let v of input){
        answer += (checkVPS(v)? 'YES': 'NO') + '\n';
    }

    console.log(answer);

    function checkVPS(ps){
        const stack = [];

        for(let v of ps){
            if(v ===')') {
                if(stack[stack.length-1] === '(') stack.pop();
                else return false;
            }
            else if(v==='('){
                stack.push(v);
            }
        }
        return !stack.length;

    }