백준 : 괄호 - 9012

 

예제 입력 1 

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1 

NO
NO
YES
NO
YES
NO

예제 입력 2 

3
((
))
())(()

예제 출력 2 

NO
NO
NO

 

이 문제는 사실 간단하다.

1. () 의 숫자가 맞아떨어지는지

2. 처음부터 )이게 나온 경우는 무시처리

 

딱 2가지만 만족하면 된다. 초반에는 count만 세고 "(" 일때는 +1, ")"일때는 -1 로 전체값이 몇인지 보려고 했었다. 하지만 2번째 경우와 같이 순서를 보장하기 어려울 것이라고 판단하여 스택을 활용하였다. 스택을 통해서 +1 대신 append, -1 대신 pop을 통해 스택이 비어있다면 동일한 짝을 지은 것이라고 생각할 수 있다. 대신 2번 조건을 유의하여 조건만 따로 해주면 된다.

import sys

input = sys.stdin.readline
result = []
n = int(input())
for i in range(n):
    stack = []
    line = input().strip() 
    is_valid = True

    for j in line:
        if j == "(":
            stack.append("(")
        elif j == ")":
            if not stack:
                is_valid = False
                break
            else:
                stack.pop()

    if not stack and is_valid:
        result.append("YES")
    else:
        result.append("NO")

for i in range(n):
    print(result[i])