[백준알고리즘/9012번/파이썬] 괄호

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

9012번: 괄호

문제: 주어진 괄호로 이루어진 문자열이 올바른 괄호 문자열인지 판단하는 문제입니다.

 

풀이 방법: stack(list)을 활용하여 '(' 에 대해서 ')'가 맞게 있는지 확인하였습니다.

 

풀이 코드:

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    stack = []
    ps = list(sys.stdin.readline().rstrip())
    vps = True

    for nps in ps:
        if nps =='(':
             stack.append(nps)
        else:
           if stack:
               stack.pop()
           else:
               vps = False
               break

    if vps and not stack:
        print('YES')
    else:
        print('NO')

 

풀이 설명:

for nps in ps:
    if nps =='(':
         stack.append(nps)
    else:
       if stack:
           stack.pop()
       else:
           vps = False
           break

여기가 핵심 코드인데요. 

 

입력 값을 하나씩 확인하면서 '(' 를 만날 경우, stack에 담아줍니다.

 

그러고 난 후, ')'를 만날 경우, stack에서 '(' 를 하나씩 pop 해주게 되면, '()'가 이루어집니다.

 

이때, ')' 가 '('  보다 많아서 입력받은 문자열은 남아있는데, stack이 빈 경우가 생기게 됩니다. 

혹은 '')(' 패턴이 들어간 경우에도 stack이 빈 경우가 생기게 됩니다. ex. ')('  '()  )(  ()'

if stack:
    stack.pop()
else:
    vps = False
    break

위 코드를 통해, stack이 비었는지 여부를 확인해주고 만약에 비었다면 ')' 갯수가 더 많은 것이므로 vps라는 변수에 False를 설정하고 break 해줍니다.

 

만약 반복문이 종료가 되었을 때, ')'  갯수가 적어서 '(' 이 남아있는 경우가 있으므로 이 부분도 신경써줘야 합니다.

if vps and not stack:
    print('YES')
else:
    print('NO')

 

위 코드와 같이, 구성해줬는데요.

vps가 True, 그리고 stack이 빈 경우에만 'YES'를 출력하고 이외에는 다 'NO'를 출력하도록 설정되어있습니다.

 

')' 갯수가 많거나 ')(' 패턴이 있다면, vps가 False 일 것이고 

')' 갯수가 적을 경우, stack에 '(' 이 남아있을 것이므로 'NO'가 출력되게 될 것입니다.