[백준]9012번: 괄호

괄호

solved_ac[Class2] 괄호

문제

괄호 문자열(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”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입력 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

예제 입력 2

6
3
((
))
())(()

예제 출력 2

NO
NO
NO

문제 해석

앞서 풀었던 [백준]4949번: 균형잡힌 세상 문제와 비슷하다. stack을 이용하여 풀면 쉽다.

풀이

• 입력 받은 문자열에서 “(“이 있는지 체크
  • 있다면 stack에 추가
• 입력 받은 문자열에서 “)”이 있는지 체크
  • 있다면 stack이 비어있는지 체크하거나 스택의 맨 위의 문자열이 “(“이 맞는지 체크
    • stack이 비어있다면 “)”의 쌍인 “(“이 없다는 것이기 때문에 NO, 그리고 스택의 맨 위 문자열이 “(“이 아니여도 짝꿍이 없는 것이기 때문에 NO. stack 초기화 후 루프 탈출
    • 둘다 아니라면 stack이 비어있지 않거나 stack 맨 위의 문자열이 “(“이라는 것이기 때문에 pop해서 없애주고 다시 루프
• 루프를 다 돌았는지 체크 (굳이 체크 안하고 2중 포문 바깥에다가 써도 됨)
  • 만약 stack이 비어있으면 같은 짝끼리 다 pop 한 것이기 때문에 YES 출력
  • 비어있지 않으면 같은 쌍을 못찾아간 문자열들이 있다는 것이기 때문에 NO 출력 후 stack 초기화

주의

sys.stdin.readline()을 통해 문자열을 입력 받으면 문자열의 마지막 문자가 \n이 출력된다. 이 문제에서는 “(“ 문자와 “)” 문자만 나왔기 때문에 개행 문자는 건들지 않았는데 else문으로 빠르게 예외처리 하고 싶다면 입력 받을때 sys.stdin.readline().rstrip()을 써서 맨 뒤에 붙는 개행문자를 제거한 채로 저장해주자!

import sys

N = int(sys.stdin.readline())

string_list = []
stk_list = []

for i in range(N):
    string_list = sys.stdin.readline()
    for j in range(len(string_list)):
        if string_list[j] == "(":
            stk_list.append("(")
        elif string_list[j] == ")":
            if not stk_list or stk_list[-1] != "(":
                print("NO")
                stk_list.clear()
                break
            else:
                stk_list.pop()
            
        if j == len(string_list) - 1:
            if not stk_list:
                print("YES")
            else:
                print("NO")
                stk_list.clear()