[백준] 9012번 괄호 (python)

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

9012번: 괄호

 

 

두 개의 괄호 "("와 ")"로 이루어진 문자열들 중 괄호의 모양이 올바르게 구성된 문자열을 구하는 문제이다. 예전에 같은 문제를 풀었던 기억이 있는데, 정답 처리가 안되어 있는 것으로 봐서는 다른 문제인 것 같다. 괄호 처리 문제는 전형적인 스택 문제라고 생각한다.

 

 

풀이 과정

1. N의 크기만큼 반복문을 돌린다. 모든 과정은 이 반복문 안에서 진행된다.
2. 반복문이 돌아갈 때마다 stack은 새로 갱신해 준다. 새 문자열이 올바른지 알기 위해서는 stack을 새로 갱신해 주어야 한다.
3. 괄호 문자열을 입력받는다.
4. 입력받은 괄호 문자열의 문자들에 접근하기 위해 반복문으로 돌려 접근한다.
   • 만약 괄호가 여는 괄호인 경우, stack에 추가해 준다. 닫은 괄호가 들어오면 언제든 올바른 괄호 짝을 이루기 때문이다.
   • 만약 괄호가 닫는 괄호인 경우, 2가지 경우를 고려해 준다.
     
     (1) stack이 비어있지 않으며 직전 괄호가 여는 괄호인 경우 "( )"는 한 쌍의 올바른 괄호 문자열이므로 pop 해준다. 즉, 직전 괄호인 여는 괄호를 삭제해 준다. 닫는 괄호는 애초에 stack에 들어가지 않는다.
     
     (2)stack이 비어있거나, 직전 괄호가 여는 괄호가 아닌 경우 닫는 괄호를 stack에 추가해 준다. 직전 괄호가 닫는 괄호인 경우 "))" 해당 문자열이 stack에 포함된다. 아마 이 경우 높은 확률로 올바르지 않은 문자열일 것이다. 
     
     
5. 마지막으로 stack의 최종 길이가 0인 경우 모든 괄호가 짝을 이루어 pop 된 것이므로 YES를 출력하고, 그렇지 않으면 NO를 출력한다. stack에 괄호가 들어있다는 것은 짝을 이루지 못해 남아있는 것이기 때문에 올바르지 않은 문자열이다.

1.  

 

정답 코드

import sys
input = sys.stdin.readline

N = int(input())

for _ in range(N):
    stack = []
    brackets = input()
    
    for bracket in brackets:
        if bracket == "(":
            stack.append(bracket)

        elif bracket == ")":
            if stack and stack[-1] == "(":
                stack.pop()

            else:
                stack.append(bracket)
                
    if len(stack) != 0:
        print("NO")

    else:
        print("YES")