백준 9012번: 괄호 (Python)

🔹 문제 설명

괄호 문자열(PS)은 (, )로만 구성된 문자열이다.
그중에서 올바른 괄호 문자열(Valid Parenthesis String, VPS)인지 판별하는 프로그램을 작성해야 한다.

✅ 올바른 VPS의 조건

1. 여는 괄호 (와 닫는 괄호 )의 개수가 같아야 한다.
2. 괄호가 올바르게 짝을 이루어야 한다.
   • 예: (())() ✅ → 올바른 VPS
   • 예: (()( ❌ → 올바르지 않음 (여는 괄호가 더 많음)
   • 예: ())( ❌ → 올바르지 않음 (닫는 괄호가 먼저 나옴)

---

🔹 내가 처음 작성한 코드

import sys
t = int(sys.stdin.readline())
stack = []
VPS_flag = True  # VPS 여부를 판별하는 변수

for _ in range(t):
    sen = sys.stdin.readline().strip()
    for char in sen:
        if char == "(":
            stack.append(char)
        else:
            if len(stack) != 0:
                stack.pop()
            else:
                VPS_flag = False  # 닫는 괄호가 더 많은 경우
    if len(stack) != 0:
        VPS_flag = False  # 여는 괄호가 더 많은 경우
    print("YES" if VPS_flag else "NO")

---

🔹 틀린 이유 분석

❌ 1. VPS_flag 초기화 문제

• VPS_flag가 한 번 False가 되면 다음 테스트 케이스에서도 영향을 미침
• 모든 테스트 케이스마다 초기화가 필요함

❌ 2. 스택 초기화 문제

• 스택(stack)을 전역 변수처럼 사용하면 이전 테스트 케이스의 데이터가 남을 수 있음
• 테스트 케이스마다 스택을 새로 초기화해야 함

❌ 3. VPS가 아닌 경우에도 계속 검사

• VPS_flag = False가 된 후에도 남은 문자를 계속 검사 → 불필요한 연산 발생
• break를 사용하여 즉시 반복문 종료하면 속도를 향상할 수 있음

---

🔹 올바르게 수정된 코드

import sys

t = int(sys.stdin.readline().strip())

for _ in range(t):
    stack = []  # 🚀 테스트 케이스마다 새로운 스택 사용
    VPS_flag = True  # 🚀 각 테스트 케이스마다 VPS 여부 초기화

    sen = sys.stdin.readline().strip()
    
    for char in sen:
        if char == "(":
            stack.append(char)
        else:  # char == ")"
            if stack:
                stack.pop()  # 짝이 맞으면 pop
            else:
                VPS_flag = False  # 닫는 괄호가 더 많음
                break  # 🚀 더 이상 검사할 필요 없음

    if stack:  # 🚀 모든 문자가 끝난 후에도 스택이 남아 있으면 VPS가 아님
        VPS_flag = False

    print("YES" if VPS_flag else "NO")

---

🔹 수정된 코드의 개선점

문제점 기존 코드 수정된 코드

VPS_flag 초기화 안 됨	VPS_flag가 전역 변수처럼 작동	🚀 for 루프 내에서 매번 초기화
스택이 리셋되지 않음	모든 테스트가 같은 stack을 공유	🚀 stack = []으로 초기화
불필요한 연산 발생	VPS_flag = False 후에도 검사 진행	🚀 break로 불필요한 연산 제거

---

🔹 실행 예제

입력

3
(())()
((()))
(()(

출력

YES
YES
NO

---

🚀 결론

✔ VPS_flag와 스택을 각 테스트 케이스마다 초기화해야 한다.
✔ 닫는 괄호가 더 많으면 break를 사용하여 불필요한 연산을 줄인다.
✔ 스택이 비어 있지 않으면 VPS가 아니므로 NO를 출력해야 한다.
✔ 최종 코드가 O(N) 시간 복잡도로 가장 효율적인 풀이 방식이다. 🚀🔥