[python] 백준 9012번 괄호 문제 풀이

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

9012번: 괄호

 

 

 

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내어야 한다. 

 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

 

 

 

 

 

---

 

 

💻 코드

 

import sys

T = int(input())

for _ in range(T):  # 테스트 개수만큼
    stack = list()

    ps = sys.stdin.readline().rstrip()  # 괄호 입력 받음
    cnt = 0  # 괄호 판단

    for i in ps:
        if i == '(':
            stack.append(i)
            cnt += 1

        else:
            cnt -= 1
            if cnt == -1:
                break

            if len(stack) != 0:
                stack.pop()

    if cnt == 0:
        print("YES")
    else:
        print("NO")

 

 

 

---

 

 

📝 풀이

 

 

괄호가 제대로 열리고 닫혔는지 판단하는 것을 구현하는 문제였는데 생각보다 처리해야하는 것이 많았다.

 

처음에 생각했던 것은 먼저 괄호가 열린 개수와 닫힌 개수가 같은지 확인하는 것이었다. cnt 변수를 통해 '('가 나오면 +1을 한 후 그것을 스택에 넣고, ')'가 나오면 -1을 하고 스택에서 '('을 pop 하여 결과가 0이 나오면 YES 아니라면 NO라고 했다. 하지만 '('보다 ')'가 먼저 나올 경우와 처음부터 ')'가 나올 경우 pop을 하면 스택에 아무것도 없는데 pop을 하여 오류가 발생하였다. 그래서 스택에 있는 원소의 개수가 0이 아닐 경우에만 pop을 하도록 수정해주었다. 이 뿐만 아니라 한 가지 케이스가 더 있었다. '('의 개수와 ')'의 개수가 같지만 위치가 잘못된 경우였다. 예를 들면, '())(()'와 같은 것이다. 이 케이스를 처리하기 위해서 ')'가 나왔을 때 cnt가 -1이 되는 경우 break를 걸어 for문을 빠져나오도록 수정하였다. cnt가 -1이 되었다는 것은 현재 열린 괄호보다 닫힌 괄호의 개수보다 더 많다는 것을 의미하기 때문이다. 최종적으로 괄호를 모두 탐색하고 for문을 빠져나오면 cnt가 0일 경우에는 YES를 해주고 cnt가 0이 아닐 경우에 NO를 해주었다.