[BOJ] 9012. 괄호

Problem

BOJ 9012. 괄호

괄호 문자열(PS)이 올바른 괄호 문자열(VPS, Valid Parenthesis String)인지 판단하시오.

Input:
6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

Output:
NO
NO
YES
NO
YES
NO

---

Initial Thought (Failed)

단순히 여는 괄호 (와 닫는 괄호 )의 개수만 비교하면 안 될까요?

• 예: )(
  • ( 개수: 1, ) 개수: 1 → 같음.
  • 하지만 올바른 괄호가 아님. 닫는 괄호가 먼저 나올 수 없음.

즉, 순서가 중요합니다.

---

Key Insight

가장 최근에 열린 괄호가 가장 먼저 닫혀야 합니다. 이는 LIFO (Last In First Out) 구조인 스택 (Stack)과 정확히 일치합니다.

• (: 스택에 넣음 (Push)
• ): 스택에서 뺌 (Pop) -> 짝을 맞춤

---

Step-by-Step Analysis

입력: (()))(

graph TD
    S1["Start"] --> C1{"Char: '('"}
    C1 -->|Push| S2["Stack: '('"]
    S2 --> C2{"Char: '('"}
    C2 -->|Push| S3["Stack: '( ('"]
    S3 --> C3{"Char: ')'"}
    C3 -->|Pop| S4["Stack: '('"]
    S4 --> C4{"Char: ')'"}
    C4 -->|Pop| S5["Stack: Empty"]
    S5 --> C5{"Char: ')'"}
    C5 -->|Stack Empty!| F["Fail: NO"]
    style F fill:#ffaaaa

1. 스택이 비어있는데 )가 나오면 NO.
2. 문자열 끝까지 갔는데 스택에 (가 남아있으면 NO.
3. 깔끔하게 비어있으면 YES.

---

Solution

import sys

# 입력 받기
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    ps = input().strip()
    stack = []
    valid = True
    
    for char in ps:
        if char == '(':
            stack.append(char)
        else:  # char == ')'
            if stack:
                stack.pop()
            else:
                # 스택이 비어있는데 닫는 괄호가 나온 경우
                valid = False
                break
            # end if
        # end if
    # end for
    
    # 1. 중간에 오류가 없었고 (valid == True)
    # 2. 스택에 남은 괄호가 없어야 함 (not stack)
    if valid and not stack:
        print("YES")
    else:
        print("NO")
    # end if
# end for

---

Complexity

• Time Complexity: $O(N)$
  • 문자열 길이만큼 한 번 순회합니다. 스택 연산은 $O(1)$입니다.
• Space Complexity: $O(N)$
  • 최악의 경우 (모두 ( 인 경우) 스택에 $N$개가 쌓입니다.

---

Key Takeaways

Point	Description
Stack	짝 맞추기, 순서가 있는 매칭 문제에 필수적
Corner Cases	스택이 비었을 때 pop, 다 끝났는데 스택이 남았을 때 체크
LIFO	나중에 들어온 놈이 먼저 나간다 (Last In First Out)