[Baekjoon] 9012 괄호(파이썬/자바스크립트/NodeJS)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

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”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

예제 입력 2

3
((
))
())(()

예제 출력 2

NO
NO
NO

 

---

정답 코드

더하기 빼기 활용
파이썬 Ver.

import sys

n = int(sys.stdin.readline().rstrip())


def answer1(n):
    for _ in range(n):
        data = sys.stdin.readline().rstrip()
        cnt = 0

        for d in data:
            if d == "(":
                cnt += 1
            else:
                cnt -= 1

            if cnt < 0:  # 마이너스가 되는 순간 더 이상 검사할 필요가 없으므로 break로 빠져나옴
                print("NO")
                break

        if cnt > 0:
            print("NO")
        elif cnt == 0:
            print("YES")


answer1(n)

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = parseInt(input[0]);
const data = input.splice(1).map((val) => val.trim());

const answer1 = (n, data) => {
    for (let i of data) {
        let cnt = 0;

        for (let j of i.split('').filter((val) => val !== '\r')) {
            if (j === '(') cnt++;
            else cnt--;

            if (cnt < 0) {
                console.log('NO');
                break;
            }
        }

        if (cnt > 0) console.log('NO');
        else if (cnt === 0) console.log('YES');
    }
};

console.log('answer1');
answer1(n, data);

 

숏코딩
파이썬 Ver.

import sys

def answer2(n):
    for _ in range(n):
        data = sys.stdin.readline().rstrip()

        while "()" in data:
            data = data.replace("()", "")

        print("NO" if data else "YES")


answer2(int(sys.stdin.readline().rstrip()))

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = parseInt(input[0]);
const data = input.splice(1).map((val) => val.trim());

const answer2 = (n, data) => {
    for (let i of data) {
        let tmp = i;

        while (tmp.includes('()')) tmp = tmp.replace('()', '');

        tmp.length > 0 ? console.log('NO') : console.log('YES');
    }
};

console.log('answer2');
answer2(n, data);

 

스택 활용 1
파이썬 Ver.

import sys

n = int(sys.stdin.readline().rstrip())

def answer3(n):
    for _ in range(n):
        stack = []
        data = sys.stdin.readline().rstrip()

        for d in data:
            if d == "(":
                stack.append(d)
            else:
                if stack:
                    stack.pop()
                else:  # 스택에 괄호가 없는 경우 짝이 맞지 않으므로 NO 반환
                    print("NO")
                    break
        else:  # break문으로 끊기지 않았을 경우 실행
            if not stack:  # 스택이 비어 있다면 괄호의 짝이 맞으므로 YES 반환
                print("YES")
            else:  # 스택에 괄호가 들어 있다면 괄호의 짝이 맞지 않으므로 NO 반환
                print("NO")


answer3(n)

자바스크립트/NodeJS Ver.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = parseInt(input[0]);
const data = input.splice(1).map((val) => val.trim());

console.log('answer2');
answer2(n, data);

const answer3 = (n, data) => {
    for (let i of data) {
        const stack = [];

        let isVPS = true;
        for (let j of i) {
            if (j === '(') stack.push(j);
            else {
                if (stack.length) stack.pop();
                else {
                    isVPS = false;
                    break;
                }
            }
        }

        if (isVPS && !stack.length) console.log('YES');
        else if (!isVPS || stack.length) console.log('NO');
    }
};

console.log('answer3');
answer3(n, data);

 

스택 활용 2

import sys

n = int(sys.stdin.readline().rstrip())

def answer4(n):
    for _ in range(n):
        stack = []
        data = sys.stdin.readline().rstrip()
        isVPS = True

        for d in data:
            if d == "(":
                stack.append(d)
            else:
                if stack:
                    stack.pop()
                else:
                    isVPS = False
                    break

        if not stack and isVPS:
            print("YES")
        elif stack or not isVPS:
            print("NO")


answer4(n)

---

문제 풀이

 문제 풀이 방법에는 크게 2가지가 있다. 하나는 cnt 변수를 선언한 다음 왼쪽 괄호와 오른쪽 괄호의 개수를 계산하여 푸는 방법이고, 나머지 하나는 스택을 활용하는 방법이다. 

 우선 괄호의 개수를 활용하는 방법을 설명하자면 반복문으로 입력값을 탐색하면서 탐색하는 값이 왼쪽 괄호('(')일 경우 개수를 증가시키고, 오른쪽 괄호(')')일 경우 개수를 감소시킨다. 이때 개수가 마이너스이거나 0보다 클 경우 짝이 안 맞는 것이므로 NO를 반환하고 개수가 0이라면 짝이 맞다는 것이므로 YES를 반환한다.

 숏코딩은 while 반복문으로 입력값을 탐색하면서 괄호 짝('()')을 replace 메서드로 빈 값으로 치환하는 작업을 data 변수 안에 괄호 짝이 존재하는 동안 반복한다. 작업을 마치고 data가 빈 값이 아니라면 NO, 빈 값이라면 괄호 짝이 맞다는 말이므로 YES를 반환한다.

 스택을 활용하는 방법은 왼쪽 괄호가 들어오면 stack에 넣고 오른쪽 괄호가 들어왔을 때는 stack을 검사해 stack이 비어 있다면 괄호의 짝이 맞지 않으므로 NO를 출력하고 break로 반복문을 중단한다. break로 반복문이 중단되지 않았을 경우 조건문을 통해 stack이 비어 있다면 괄호의 짝이 맞으므로 YES, stack이 비어 있지 않다면 NO를 반환한다.

---

함께 보기

https://wookcode.tistory.com/49

[백준] 9012번 괄호 (Python)

https://velog.io/@ms269/%EB%B0%B1%EC%A4%80-9012-%EA%B4%84%ED%98%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python

[백준] #9012 - 괄호 (파이썬, Python)

https://omins.tistory.com/34

백준 9012번 파이썬

https://bio-info.tistory.com/123

[백준] 9012 - 괄호 (Python, 숏코딩 포함)