[Python] 백준 9012번(괄호) 문제 풀이

 

for i in range(int(input())):
    stack = []
    S = input()
    printed = False
    for char in S:
        if char == "(":
            stack.append(char)
            continue
        try:
            stack.pop()
        except:
            print("NO")
            printed = True
            break
    if printed:
        continue
    if len(stack) != 0:
        print("NO")
        continue
    print("YES")​

 

스택 자료구조를 사용해서 문제를 풀었다. "("이라면 스택에 넣어주고, ")"이라면 마지막으로 추가된 "("을 스택에서 빼주다가 스택에 더 이상 ")"에 매칭되는 "("이 존재하지 않거나 "("이 ")"보다 많은 경우에는 "NO"를, "("과 ")"의 수가 같을 경우(스택의 길이가 0인 경우)에는 "YES"를 출력해 주는 알고리즘이다.