백준 문제 중 , 스택, ‘괄호’

백준 문제 중 9012번

https://www.acmicpc.net/problem/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”를 한 줄에 하나씩 차례대로 출력해야 한다.

---

풀이

스택을 활용해서 문자열 스캔중에 ( 를 만나면 스택에 저장하고 ) 를 만나면 스택에서 ( 를 팝해 모든 ( 가 스택에서 비워진다면 문제의 조건을 만족한다고 판단할 수 있을것이다.

주의 할점은 스택이 비었을때 ) 를 만나다면 pop을 멈추고 vps가 아니므로 종료 해야하고, 처음 스캔된 문자열이 ( 이 아니라면 조기종료를 시켰다.

 # 입력처리
T = int(input())

x = [None]*T

for i in range(T): x[i] = input()

 # 출력을 위한 문자열 선언
y,n = 'YES','NO'
 
 # vps 여부를 확인하는 함수
def is_vps(ps:str)->bool:

     # 스택으로 다룰 리스트 선언
    tmp = []

    for i in range(len(ps)):

         # 첫 시작이 ( 이 아니라면 조기종료
        if ps[0]!='(':
            return False
        else:

             # 스캔중 ( 를 만나면 스택에 저장
            if ps[i]=='(':
                tmp.append('(')

             # 스캔중 )를 만나다면 스택의 ( 팝
            elif ps[i]==')':

                 # )를 만났는데 스택이 비어있다면 false
                if tmp:
                    tmp.pop()
                else:
                    return False

    return False if tmp else True

for i in range(T):
    if is_vps(x[i]):
        print(y)
    else:
        print(n)

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(
NO
NO
YES
NO
YES
NO