백준 9012번. 괄호 (파이썬)

문제

 

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

9012번: 괄호

 

 

 

문제 풀이과정

여는 괄호를 만나면 스택에 넣어주고, 닫는 괄호를 만나면 스택에서 빼낸다는 것이 주요 포인트!!

 

1. 여는 괄호가 있으면, 무조건 닫는 괄호가 있어야한다.

 

2. 반복문으로 입력받은 문자열을 탐색하면서 여는 괄호를 만나면 스택에 넣어준다.

 

3. 닫는 괄호를 만나면 스택에서 빼내는데, 만약 스택이 비어있다면 여는 괄호 < 닫는 괄호 상태로 짝이 맞지 않기 때문에 'NO'를 출력한다.

 

4. 문자열 탐색이 끝난 후 스택이 비어있다면 괄호의 짝이 맞는 것이므로 'YES'를 출력하고, 그렇지 않다면 여는 괄호 > 닫는 괄호 상태로 짝이 맞지 않기 때문에 'NO'를 출력한다.

 

 

import sys
t=int(input())
for _ in range(t):
    s=sys.stdin.readline().strip()
    stack=[]
    already=False
    for x in s:
        if x=='(':
            stack.append('(')
        else:
            if stack==[]:
                print('NO')
                already=True
                break
            stack.pop()
    if stack:
        print('NO')
    elif stack==[] and already==False:
        print('YES')

 

 

 

더 나은 풀이

 

스택을 이용하지 않고 여는 괄호와 닫는 괄호의 수를 세어 짝이 맞는 지 판별한다.

 

import sys
t=int(input())
for _ in range(t):
    s=sys.stdin.readline().strip()
    cnt=0
    already=False
    for x in s:
        if x=='(':
            cnt+=1
        else:
            cnt-=1
            if cnt<0:
                break
    if cnt==0:
        print('YES')
    else:
        print('NO')