[Python] 백준 9012번: 괄호

t = int(input())

for _ in range(t):
    input_str = input()
    stack = []
    for j in input_str:
        if j == '(':
            stack.append(j)
        elif j ==')':
            if stack:
                stack.pop()
            else:	# stack이 비어버렸는데 )가 나오면 No 출력
                print('NO')
                break
    else:	# break로 빠지지 않을 시 진행
        if not stack:
            print('YES')
        else:
            print('NO')

백준 사이트에 괄호라는 문제를 풀어보았습니다.

간단하게 설명하면 말 그대로 괄호를 열고 닫는 문제입니다. 이것을 VPS(Valid PS)라고 부릅니다. 올바르게 괄호가 열리고 닫힌다면 Yes를 괄호가 닫히지 않는다면 NO를 출력하는 문제입니다.

 

 

https://www.acmicpc.net/problem/9012

 

* 문제 풀이

먼저 저의 풀이 방법은 괄호를 열면 cnt를 +1 닫으면 -1을 해주는 코드를 작성하였습니다.

 

t = int(input())

for _ in range(t):
    string_list = list(input())
    cnt = 0
    for j in string_list:
        if j == '(':
            cnt += 1
        elif j == ')':
            cnt -= 1
    
    if cnt == 0:
        print('YES')
    else:
        print('NO')

 

해당 코드의 문제점은 예제 입력 2에서 가장 마지막 문제에서 발생합니다. 괄호가 ()) 에서 끝나서 이미 VPS를 만족하지 못하지만 저의 코드대로 동작하게되면 괄호의 갯수는 맞기 때문에 YES의 정답이 나오게 됩니다.

 

그래서 저는 stack을 이용하기로 하였습니다.

 

( 입력시 stack에 append를 해주고, )가 나오면 pop을 해주어서 만약 stack이 비었을 시 )가 나오게되면 break를 걸어 NO가 출력이 되게 해주는 코드를 작성하게 되었습니다.