[BOJ] 9012. 괄호

📌 문제 제목

문제 링크: BOJ 9012

---

🗒️ 문제 설명

VPS: 괄호의 모양이 바르게 구성된 문자열

괄호 문자열이 주어질 때, VPS인지 판별하는 프로그램

시간 제한: 1초

메모리 제한: 128MB

---

💡 문제 해결 아이디어

• ps를 순회하며 여는 괄호는 스택에 추가
• 닫는 괄호는 스택의 마지막 원소가 여는 괄호일 경우 pop
• 순회가 끝나고 스택에 원소가 남아있으면 False, 아니면 True

---

⌛️ 시간 복잡도

• O(L_1 + L_2 + ... + L_N) = O(T). T는 모든 입력 문자열의 총 길이

---

✅ 최종 코드

import sys
input = sys.stdin.readline

N = int(input().strip())


def isVPS(ps: str) -> bool:
    stk = []
    for b in ps:
        if b == '(':
            stk.append(b)
        else:
            if stk and stk[-1] == "(":
                stk.pop()
            else:
                return False
    return True if not stk else False


for _ in range(N):
    ps = input().strip()
    print("YES" if isVPS(ps) else "NO")