백준 9012번 : 괄호 in Python

9012번: 괄호

 

www.acmicpc.net

이 문제는 "("와 ")"로만 이루어진 문자열인 괄호 문자열이 주어질 때 괄호의 모양이 바르게 구성되었는지를 확인하는 문제이다.

괄호 문자열은 "("이 나올 경우 이에 대응하는 ")"가 반드시 나와야 한다. 이를 제대로 구현하기 위해서는 스택을 이용하면 된다. 문자열의 각 문자에 대해 순회하면서 만약 문자가 "("라면 스택에 넣고, ")"라면 스택의 맨 위에 있는 문자 "("를 제거한다. 이때 만약 스택이 비어있으면 ")"와 대응하는 "("가 없다는 뜻이므로 "NO"를 출력한다. 또한 이러한 과정을 모두 거쳤을 때 스택에 문자가 남아있다면, 스택에 남아있는 "("에 대응하는 ")"가 없다는 뜻이므로 "NO"를 출력한다. 만약 두 경우 모두 아닌 경우에는 모든 "("가 ")"와 적절히 대응한다는 뜻이므로 "YES"를 출력한다.

이를 코드로 구현하면 다음과 같다,

T = int(input())
for _ in range(T):
    s = input()
    stack = []
    res = True
    for c in s:
        # 문자가 "("이면 stack에 넣는다.
        if c == "(":
            stack.append("(")
        # 문자가 ")"이면 stack에서 "(" 하나를 제거한다.
        else:
            if len(stack) > 0:
                stack.pop()
            # 제거할 "("가 없는 경우 ")"에 대응하는 "("이 없는 경우이므로 "NO"를 출력한다.
            else:
                res = False
                break
    # stack이 비어 있지 않은 경우에도 "("에 대응하는 ")"가 없는 경우이므로 "NO"를 출력한다.
    if not res or len(stack) > 0:
        print("NO")
    else:
        print("YES")