백준 9012번 괄호 - 파이썬

9012번: 괄호

stack자료구조를 생각해서 문제를 풀면 금방 풀 수 있다. 하지만 반례가 있는지 틀렸다..

문제에 나와있는 예시는 모두 다 정답인데,, 질문검색 목록에 여러 반례를 찾아보았다.

반례는 ')(' 이 문자열이었다. 이 경우에는 올바른 괄호가 아닌 경우다. 

내가 올바른 괄호를 잘못 이해한 부분은 서로 다른 괄호가 만나면 상쇄된다고만 생각했다.

하지만 닫는 괄호가 먼저 오고 여괄호가 오는 구조는 올바른 괄호가 아닌 것이다.

처음 코드 - 틀림

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    arr = ""
    stack = []
    arr = input().rstrip()
   
    for i in arr:
        if not stack:
            stack.append(i)
        else:
            if stack[-1] != i:
                stack.pop()
            else:
                stack.append(i)
    
    if stack:
        print("NO")
    else:
        print("YES")

성공 - 반례 추가

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    arr = ""
    stack = []
    arr = input().rstrip()
   
    for i in arr:
        if not stack:
            stack.append(i)
        else:
            if stack[-1] != i:
                if stack[-1] == ")":
                    stack.append(i)
                else: stack.pop()
            else:
                stack.append(i)
    
    if stack:
        print("NO")
    else:
        print("YES")

# 올바른 괄호는 여괄호가 닫는 괄호와 쌍을 이루어 만났을 때일 뿐이다.
# )( 와 같은 예시는 올바를 괄호가 아님.