[백준 9012][파이썬] 괄호 문제

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

9012번: 괄호

괄호 모양이 올바른 괄호 모양인지 판단하는 문제이다.

 

올바른 괄호 모양의 정의를 다음과 같이 내렸다.

 

1. '(' 모양의 개수를 left, ')' 모양의 개수를 right로 정한다.

 

2. 문자열의 앞에서부터 left와 right를 증가시키는 과정에서 left는 항상 right 보다는 같거나 커야한다. 

 

3. 한 문자열을 전부 조사하고 나면 left와 right의 개수는 반드시 같아야 한다.

 

import sys 
n=int(sys.stdin.readline())
for _ in range(n):
    ps=sys.stdin.readline().strip('\n')
    left=0
    right=0
    con=False
    for i in ps:
        if i=='(':
            left+=1
        else:
            right+=1
        if right>left:
            print("NO")
            con=True
            break
    if con:
        continue
    if left==right:
        print("YES")
    else:
        print("NO")

 

나는 이렇게 풀었으나 사실 이 문제의 출제 의도는 스택을 활용한 문제풀이이다.

 

쉬운 문제라 스택을 사용하지 않아도 풀 수 있었으나 스택을 활용하면 문제 풀이에 더욱 적합한 풀이가 된다.

 

1. '(' 문자를 만날 때마다 스택에 문자를 추가한다.

 

2. ')' 문자를 만나면 스택에서 '(' 문자를 제거한다. 제거할 '(' 문자가 없으면 올바르지 않은 괄호 모양이다.

 

3. 한 문자열을 전부 조사하고 나면 스택이 비어있어야 한다.

 

list를 스택처럼 사용해도 되지만 스택에 들어가는 문자는 '(' 문자 하나이기 때문에 그냥 정수형 변수 만들어서 1을 더하고 빼는 식으로 구현하는 편이 쉽다.

 

<스택을 활용한 방식>

import sys 
n=int(sys.stdin.readline())
for _ in range(n):
    ps=sys.stdin.readline().strip('\n')
    stack=0
    con=False
    for i in ps:
        if i=='(':
            stack+=1
        else:
            stack-=1
        if stack<0:
            print("NO")
            con=True
            break
    if con:
        continue
    if stack==0:
        print("YES")
    else:
        print("NO")