[JS] 백준 9012번 괄호

 

출처

백준 온라인 저지

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로 나타내어야 한다. 

풀이

기호 '('와 ')'의 개수를 카운트하여 '(' 기호 일 시 1을 더해주고 ')' 기호 일 시 1을 빼줍니다.

만약 VPS 인 문자열일 시 '(' 기호와 ')' 개수가 서로 딱 떨어지므로 0이 나오게 됩니다.

 

카운트된 수가 -1이 될 시 닫치지 않는 ')' 기호가 존재한다는 뜻이므로 해당 문자열은 VPS가 아닌 문자열이 됩니다.

 

코드

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

const len = input.shift();
const result = [];

for (let i = 0; i < len; i++) {
    let cnt = 0;
    
    for (let s of input[i]) {
        cnt += s === "(" ? 1 : -1;
        
        if (cnt < 0) break;
    }
    
    result.push(cnt === 0 ? 'YES' : "NO");
}

console.log(result.join('\n'));

 

다른 방식

괄호를 없애는 방법으로 결과를 구하는 코드를 생각해보았습니다.

 

정규식으로 ()을 한 묶음으로 보고 없애주고 만약 문자열에 변화가 생길 시 한 번 더 replace를 시켜줍니다.

만약 더 이상 없앨 기호 묶음이 존재하지 않으면 "NO"가 나올 수 있는 조건은 두 가지가 있습니다.

 

남은 문자열의 맨 앞이 ")" 기호 이거나 문자열의 맨 뒷 기호가 "(" 일시 VPS이 아닌 문자열이 됩니다.

 

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

const len = input.shift();
const result = [];

function removeStr(str) {
  const resultStr = str.replace(/\(\)/g, '');

  if (str.length !== resultStr.length) {
    return removeStr(resultStr);
  }

  return str[0] === ")" || str[str.length-1] === "(" ? "NO" : "YES";
}

for (let i = 0; i < len; i++) {
  result.push( removeStr(input[i]) );
}

console.log(result.join('\n'));