[백준 9012번 괄호 - node.js] [알고리즘 기초 1/2]

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

9012번: 괄호

 

문제

 

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

 

입력

 

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

 

출력

 

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

예제 입출력

 

입력	출력
6 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()(	NO NO YES NO YES NO
3 (( )) ())(()	NO NO NO

 

풀이[node.js]

 

 

728x90

[가장 간단한 방식]

이번 문제는 두 가지 방법으로 풀어보았는데, 가장 간단한 방법을 소개해드리겠습니다.

괄호 ()이 페어로 있어야만 하는건데, (는 +1, )는 -1로 값을 정해서 더해주게 되는 방식입니다.

( 이 나와서 +1이 되었는데, ) 이 두번 나와 -1로 음수값이 나오면 페어가 안되는 것이기 때문에, (닫혔지만, 열린 괄호가 없음) 이는 바로 VPS가 아니기 때문에, break문을 타고 나오게 로직을 구현하였습니다.

만약, 페어가 맞아서 +1, -1이 잘 이루어져 값이 0이라면, 페어이므로 answer에 YES를 넣어주고, 이 외의 값들(break문으로 나온경우 포함)은 모두 NO로 answer에 넣어주면 됩니다.

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(input[0]);
var answer ='';
for(var i=1; i<=cases; i++){
    var test = 0;
    var splited = input[i].split('');
    for(var j in splited){
        if(test <0){
            break;
        }else{
            if(splited[j] === '('){
                test += 1;
            }else{
                test -= 1;
            }
        }
    }
   if(test === 0){
        answer += 'YES' + '\n';
    }else{
        answer += 'NO' + '\n';
    } 
}

console.log(answer);

[stack 이용한 정석]

 

아래는 stack을 이용한 가장 정석의 방식입니다.

우선 들어온 input의 배열의 요소를 split('')으로 괄호들을 각각 뜯어주었고, 첫번째 값은 stack에 집어넣은 후,

for문을 돌면서 stack에 가장 마지막에 있는 값이 ( 이고, 들어올 값이 ) 이면 fair이므로 stack의 마지막 값을 제거해줍니다.fair가 아니라면, splited[j]값을 stack에 넣어줍니다.입력된 값이 fair가 된다면, stack의 길이는 0일 것이므로, YES값을 넣어주고, 아니라면 fair가 아니기 때문에, answer에 NO를 넣어주면 됩니다.

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(input[0]);
var stack = [];
var answer ='';
for(var i=1; i<=cases; i++){
    var splited = input[i].split('');
    stack.push(splited[0]);
    for(var j=1; j<splited.length; j++){
        if(stack[stack.length-1] === '(' && splited[j] === ')'){
            stack.pop();
        }else{
            stack.push(splited[j]);
        }
    }
    if(stack.length === 0){
        answer += 'YES' +'\n';
    }else{
        answer += 'NO' +'\n';
    }
    stack=[];
}
console.log(answer);

 

[가장 복잡한 방식]

아래는 제가 조금 복잡하게 푼 방식입니다.

위의 방식이 더욱 간단할 것 같습니다.

배열의 길이의 2/1만큼만 돌면서 페어한 값이 아닌 값들만 tmp배열에 넣어주는 방식입니다.

만약 배열을 나눈 값이 홀수라면, 페어할 수 없으므로, answer값은 자동으로 NO가 됩니다.

 

만약 splited[j]값이 (라면, 그 다음 값이 (이거나 다음 값이 없을 경우엔, 닫히지 못한 것이므로, tmp에 값을 넣어줍니다.

그리고, splited[j]값이 )인 경우엔, 그 앞의 값이 )이거나 다음 값이 없을 경우엔, 닫지 못한 것이므로, tmp에 넣어줍니다.

이렇게 앞뒤로 열리고 닫힌 괄호들이 아닌 페어가 아닌 값들만 tmp에 남도록 for문을 돌았을 때, tmp의 길이가 0이면, 모두 페어한 것이기에 YES를, 값이 남아있다면 NO를 넣어줍니다.

 

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(input[0]);
var answer ='';
for(var i=1; i<=cases; i++){
    var splited = input[i].split('');
    if(splited.length%2 === 0){
        var len = splited.length/2;
        for(var k=0; k<len; k++){
            var tmp = [];
            for(var j=0; j<splited.length; j++){
                if(splited[j] === '('){
                     if(splited[j+1] === '(' || splited[j+1] === undefined){
                          tmp.push(splited[j]);
                     }
                }else if(splited[j] === ')'){
                     if(splited[j-1] === ')' || splited[j-1] === undefined){
                         tmp.push(splited[j]);
                      }
                }
            }
            splited = tmp;
        }
        if(tmp.length === 0){
            answer += 'YES' + '\n';
        }else{
            answer += 'NO' + '\n';
        }
    }else{
        answer += 'NO' + '\n';
    }
}
console.log(answer);