[Python] 백준 9012 괄호

문제

입력으로 주어진 괄호 문자열이 올바른 괄호 문자열(Valid PS, VPS)인지 해당 여부 확인

 

 

입력

• 첫째 줄:  입력 데이터의 수를 나타내는 정수 T
• T개의 줄:  괄호 문자열 (2 이상 50 이하)

 

 

출력

올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력

 

 

 

---

★Key Point : 스택

 

 

<TryCode : 틀렸습니다>

n = int(input())
for _ in range(n):
    list = input()
    left = 0; #왼괄호
    right = 0; #오른괄호
    for i in list:
        if i == '(':
            left += 1
        else:
            right += 1
    print('NO' if left != right else 'YES')

 

괄호의 개수 비교만 하면 해결할 수 있을 거라고 생각했지만, 다른 풀이방식을 요구했다.

 

 

 

<최종 CODE>

n = int(input())

for _ in range(n):
    lst = list(input())
    stack = []
    for i in lst:
        if i == "(":
            stack.append(i)
        elif i == ")":
            if not stack or not stack.pop(): #스택에 아무것도 없거나 pop() 처리 안했다면
                print("NO")
                break
    else: #for문을 다 돌고 처리하는 조건문
        if not stack: #괄호의 짝 수가 맞아서 스택이 빌 때
            print("YES")
        else: #스택이 비어있지 않을 때, 왼쪽 괄호 수가 더 많을 때
            print("NO")

 

스택을 사용할 때는 push() 할 때와 pop() 할 때의 조건을 설정해주어야 한다.

모든 문자열을 다 push() 하지 않는 것이 효율적이므로 기준이 되는 '(' 여는 괄호만 넣기로 결정했다.

 

 

 

자료구조 시간에 배운 스택, 설명이 담겨 있는 슬라이드

 

 

위 사진은 자료구조 수업 당시 스택에 대해 배우면서 예제로 다뤘던 중위 수식-> 후위 수식 변환하는 방법이 담긴 슬라이드이다. 

 

이 방법을 참고하여 괄호 검사를 해보면, 

'('을 만나면 stack에 넣고,  ')' 을 만나면 가장 최근에 넣은 '('을 pop해주는 형식이다. 다른 연산자나 숫자가 입력되는 것이 아니기 때문에 순서는 상관없다. 중요한건 pop()처리와 stack이 비어 있는지 여부를 확인하는 것.