[Python] [백준] 9012번 - 괄호 (stack 사용)

문제

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

---

예전에 stack문제를 쉽게 푸는 방법을 봤었다.

() 모양을 0으로 replace 해주면 쉽게 풀린다.

 

이 문제에서는 ()를 없애면, 그 외곽의 괄호가 붙어

()가 다시 생기고, 이것을 다시 없애는 식으로 풀었다. 

import sys
N = int(sys.stdin.readline())
for _ in range(N):
	T = sys.stdin.readline()
	T = T.replace("\n", "")
	if len(T) != 0:
		while "()" in T:
			T = T.replace("()", "")
		if len(T) == 0:
			print("YES")
		else:
			print("NO")

입력을 받으면 \n도 배열의 끝에 들어와서

\n도 ""로 치환하여 없앴다.

 

()가 입력받은 문자열에 있다면

()를 ""로 치환하여 없애고,

 

이렇게 반복하면 ()이 단계별로 사라진다.

()가 다 사라진 후에, T가 비었다면 VPS이므로 YES를 출력하고,

T에 문자가 남아있다면 VPS가 아니므로 NO를 출력한다.

 

하지만 stack 문제를 stack으로 푼 것이 아니라서

stack으로도 풀어보았다.

---

import sys
N = int(sys.stdin.readline())
for _ in range(N):
    T = sys.stdin.readline()
    stack = []
    T = T.replace("\n","")
    for vps in T:
        if vps == "(":
            stack.append(vps)
        elif vps != "(" and "(" not in stack:
            stack.append(vps)
        elif vps != "(" and "(" in stack and len(stack) != 0:
            stack.pop()
    if len(stack) == 0:
        print("YES")
    else:
        print("NO")

입력을 받으면 \n도 배열의 끝에 들어와서

\n도 ""로 치환하여 없앴다.

 

그리고 stack 답게 ( 가 들어오면 쌓고,

) 가 들어오면 ( 을 없애는 식으로 작성했다.

( 가 없다면 ) 는 쌓인다.

 

그렇게 stack의 길이가 0이 되면 YES를 출력하고,

아니라면 NO를 출력한다.