[BOJ/PYTHON] 9012. 괄호

백준 문제 링크: https://www.acmicpc.net/problem/9012

문제 요약

입력으로 주어진 괄호 문자열이 VPS인지 판단 올바른 괄호 문자열(Valid PS, VPS)은 괄호 짝 잘 지어진 문자열

핵심 아이디어

전형적인 스택 문제다. 괄호 모양을 보고 스택에 넣어주거나 빼면 된다.

)가 왔을 때 스택에서 무조건 빼주는 게 아니라, 스택 맨 위가 ( 모양이면 빼주면 된다.

풀이

# silver4-9012. 괄호

import sys 
input = sys.stdin.readline

t = int(input()) 
for _ in range(t):
    stack = [] # 테스트 케이스마다 스택 초기화
    ps = input().rstrip() # 각 줄 입력
    for i in range(len(ps)):
        if ps[i] == "(":
            stack.append("(")        
        # )가 오고 스택 맨 위가 (일 때
        elif ps[i] == ")" and stack and stack[-1] == "(": 
                stack.pop()
        else:
            stack.append("-")
    # 정답 출력: 스택에 - or (가 남아있으면 올바른 괄호 문자열이 아님
    if stack: print("NO")
    else: print("YES")

실행 시간

메모리 31256KB, 시간 44ms (python3)