[boj] 9012. 괄호

[boj] 9012. 괄호

• 문제 링크 : https://www.acmicpc.net/problem/9012
• 사용 언어 : Node.js

9012번: 괄호

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

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

1. 문제 분석

이 문제는 주어진 문자열 내에 있는 괄호들이 모두 쌍을 이루는지 확인하는 문제 입니다. 힌트는 괄호쌍은 반드시 다른 괄호쌍에 의해서만 감싸질 수 있다는 점입니다. 이는 가장 바깥에 있는 괄호로부터 안으로 들어갈 때 중간지점을 기준으로 대칭을 이룬다는 것입니다. 곧 앞에서부터 세었을 때 중간 지점에서는 앞에서 세었던 것으로부터 역순으로 끝나야 옳은 괄호 문자열 ( VPS )가 된다는 것을 뜻합니다. 들어온 순서의 역순? Stack을 활용 할 수 있겠습니다.

---

2. 솔루션

const fs = require('fs')
const [T, ...cases] = fs.readFileSync(process.platform ===
                                      'linux' ? '/dev/stdin' : 'input.txt')
                        .toString().split('\n').map(input => input.trim());

function isValid(sentence) {
    const groupOfParenthesis = [...sentence];
    const stack = [];
    while (groupOfParenthesis.length > 0) {
    	// 문장의 가장 앞 괄호 꺼내기
        const parenthesis = groupOfParenthesis.shift();
        // 여는 괄호라면 Stack에 Push
        if (parenthesis === '(') {
            stack.push(parenthesis);
        // 닫는 괄호라면 ... 
        } else {
            const top = stack[stack.length - 1]
            // Stack의 Top이 여는 괄호라면 짝지어 제외 '()'
            if (top === '(') {
                stack.pop();
            // Stack의 Top이 닫는 괄호라면 올바르지 않은 괄호쌍 '))'
            } else {
           
                return false;
            }
        }
    }
    // Stack이 비워 졌다면 모든 괄호가 쌍을 이루었으므로 옳은 문장
    // Stack이 남아 있다면 여는 괄호가 쌍을 못 이뤘으므로 잘못된 문장
    return stack.length === 0;
}

const countOfTests = +T;
const groupOfCases = cases.map(c => [...c])
let answer = [];
for (let i = 0; i < countOfTests; i++) {
    const sentence = groupOfCases[i];
    answer.push(isValid(sentence) ? "YES" : "NO");
}
console.log(answer.join('\n'))

마치며

바람직하지 않은 방법이지만 사실 알고리즘 풀이를 할 때마다 괄호? 역순? 뒤집기? 를 볼 때마다 척수반사로 Stack이 떠올라 버립니다. 
이런 저 괜찮은 걸까요? 
다른 분들 풀이를 보니 Stack에는 항상 여는 괄호만 들어간다는 것을 활용하여 여는 괄호의 개수만을 이용해 풀이 또한 존재했습니다. 해당풀이를 소개하며 이번 포스팅을 마치겠습니다.
감사합니다.

const fs = require('fs')
const [T, ...cases] = fs.readFileSync(process.platform ===
                                      'linux' ? '/dev/stdin' : 'input.txt')
                        .toString().split('\n')
                        .map(input => input.trim());
const countOfCases = +T;

function isValid(sentence) {
    const charsOfSentence = [...sentence];
    let count = 0;
    for (const char of charsOfSentence) {
        if (char === '(') {
            count++;
        } else {
            count--;
        }
        if (count < 0) {
            return false;
        }
    }
    return count === 0;
}

let answer = [];
for (let i = 0; i < countOfCases; i++) {
    const sentence = cases[i];
    answer.push(isValid(sentence) ? "YES" : "NO")
}
console.log(answer.join('\n'))