[백준/python] 9012번: 괄호

문제

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

9012번: 괄호

---

문제 설명

T개의 테스트 데이터 괄호문자열을 받고 올바른 괄호 문자열(Valid PS, VPS)인지 판별하여

'NO' 또는 'YES'를 출력하는 문제이다.

---

코드

T = int(input())

for _ in range(T):
    arr = list(input().strip())  # 입력 문자열을 공백 및 개행 문자 제거 후 리스트로 변환
    stack = []  # 스택으로 활용할 리스트

    for char in arr:
        if char == "(":
            stack.append(char)
        elif char == ")":
            if stack and stack[-1] == "(":  # 스택이 비어있지 않고, 짝이 맞는 "("가 스택의 맨 위에 있는 경우
                stack.pop()
            else:
                stack.append(char)

    if not stack:  # 스택이 비어있으면 모든 괄호가 짝이 맞음
        print("YES")
    else:
        print("NO")

---

코드 설명

반복문을 통해 괄호를 확인하고 조건에 맞게 스택에 push, pop 해준다.

1. '(' 라면, 그냥 스택에 push해준다.

2. ')' 라면, 스택이 비어있지 않고 짝에 맞는 '('가 스택 맨 위에 있는지 확인한다.

3. 조건에 맞다면 스택에서 맨 위에 있는 괄호 '('를 pop해준다.

4. 조건에 맞지 않다면 ')'을 넣는다.

+ 스택에 들어간 ')'는 pop되지 않으므로 반복문이 종료된 후에도 스택에 남게 된다.

5. 반복문이 종료되고 스택이 비어있으면 모든 괄호가 짝이 맞았다는 뜻이므로, 'YES'를 출력한다.

6. 만약 스택이 비어있지 않다면 처리되지 않은 괄호가 남아있다는 뜻이므로, 'NO'를 출력한다.

---

이 문제의 핵심은 바로 닫힌 괄호 ')'이다.

닫힌 괄호가 스택에 쌓인 열린 괄호보다 많이 들어온 순간, 이미 그 문자열은 VPS가 성립되지 않는다.

추가적으로 '('와 ')'의 개수만 같다고 해서 VPS가 되지않는다.

예를 들어, '())(()' 같은 입력은 개수가 같지만 처리될 수 있는 열린 괄호가 없는 상태에서 닫힌 괄호가 먼저 등장했기 때문에 올바른 괄호 문자열이 아니다.