백준 9012번 괄호

[문제 LINK]
https://www.acmicpc.net/problem/9012

한 쌍의 괄호 기호로 된 문자열인지 아닌지를 판단하는 문제이다.

해결 TIP

주어진 입력값이 한 쌍의 괄호로 이루어져있는지 판단하기 위해서는 가장 안쪽에서 한쌍으로 존재하는 괄호부터 제거해나가면 바깥쪽도 한쌍으로 만날 수 있게된다.

이렇게 되면 한쌍으로 이루어진 괄호들은 다 제거되어 아무것도 남지 않게된다.

결국 다 제거되면 VPS이고 아니면 VPS가 아니다.

이 문제를 쉽게해결하기 위해 필자는 큐를 사용했다.

만약 입력값 ( ( ) ) ( ) )이 주어졌다면 왼쪽부터 하나씩 큐에 넣어가면서 한쌍을 이루게 된다면 제거하는 식으로 해결하였다.

길이가 7인 입력값의 큐와 입력값의 변화모습을 그림으로 나타낸 모습이다.

좌측에 위치한 네모도형이 큐의 상태 우측에 위치한 네모도형은 입력값이다.

0. 입력값의 맨 처음 값인 ( 가 큐에 쌓이고 우측 입력값은 하나가 줄어든 모습이다.
1. 입력값의 두 번째 값인 ( 가 큐에 쌓이고 우측 입력값은 하나가 줄어든 모습이다.
2. 입력값의 세 번째 값과 큐의 마지막 값이 한쌍을 이루고 있기 때문에 세 번째 입력값은 큐에 넣지 않고 기존에 쌓아놨던 값을 제거한 모습이다.
3. 입력값의 네 번째 값과 큐의 마지막 값이 한쌍을 이루고 있기 때문에 네 번째 입력값은 큐에 넣지 않고 기존에 쌓아놨던 값을 제거한 모습이다.
4. 입력값의 다섯번째 값이 큐에 추가된 모습이다.
5. 입력값의 여섯번째 값과 큐의 마지막 값이 한쌍을 이루고 있기 때문에 여섯번째 값은 큐에 넣지 않고 기존에 쌓아놨던 값을 제거한 모습이다.

마지막으로 남은 일곱번째 입력값 )만 큐에 남게 되므로 입력값은 다 없어지지않고 남아있기에 해당 입력값은 VPS가 아니다.

전체코드

from collections import deque

n = int(input())

for i in range(n):
    s = input()
    q = deque()
    
    for j in s:
        if q and q[-1] == '(' and j == ')':
            q.pop()
            continue
        q.append(j)
        
    if q:
        print('NO')
    else:
        print('YES')