[Python] 백준 알고리즘 문제풀이 :: 9012번

파이썬을 이용한 백준 알고리즘 9012번 괄호 문제풀이. 스택으로 분류되어 있는 걸 생각하면 쉽게 풀린다. 그런데 스택을 생각하지 못한다면 은근 복잡하게 느껴지는 문제. 한 3분 이거 규칙을 어떻게 파악하지 생각했다. 그러다 문득 스택 문제집에 들어있다는 걸 생각하니 바로 해결책이 떠올랐다.

문제

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

풀이

import sys
 
tc = int(sys.stdin.readline())
 
for t in range(0, tc):
    flag = 1
    stack = []
    ps = sys.stdin.readline().rstrip()
 
    for i in range(0, len(ps)):
        if ps[i] == "(":
            stack.append(1)
        elif ps[i] == ")":
            if len(stack) == 0:
                flag = 0
                break
            else:
                stack.pop()
 
    if len(stack) != 0:
        flag = 0
 
    if flag == 1:
        print("YES")
    else:
        print("NO")

vps인지 아닌지를 판단할 변수 flag를 1로 선언한다.

괄호를 담을 빈 리스트 stack을 선언한다.

문자열을 입력받고 각 문자열을 확인한다.

만약 문자가 "("이면 스택에 집어넣는다.

문자가 ")"이면 스택에서 뺀다. 만약 stack의 길이가 0이라면, 여는 괄호 "("가 없이 닫는 괄호가 들어간 것이므로 vps가 아니다. flag를 0으로 바꾸고 for문에서 나간다.

만약 길이가 0이 아니라면 입력된 ")"에 대응하는 "("가 하나 이상 있는 것이다. ")를 넣는 게 아니라 "("를 빼준다. 테트리스처럼 입력된 "("에 상응하는 ")"가 오면 블럭을 없앤다는 느낌.

문자열의 모든 문자를 확인하고, vps라면 모든 "("에 상응하는 ")"가 있었던 것이므로 stack 길이가 0일 것이다. 아니라면 vps가 아니므로 flag를 0으로 바꾼다.

flag에 따라 "YES" 또는 "NO"를 출력한다.