문제

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

 

내 제출

count = int(input())
for i in range(count) :
    stack = [] # 괄호를 넣을 stack list
    lst = input()
    lst = list(lst)
    for j in lst :
        if j == '(' :
            stack.append('(')
        elif j == ')' :
            if len(stack) != 0 and stack[-1] == '(' :
                stack.pop()
            else :
                stack.append(')')
                
    if len(stack) == 0 : # VPS임
        print("YES")
    else : 
        print("NO")

해설

count = int(input())
for i in range(count) :
    stack = [] # 괄호를 넣을 stack list
    lst = input()
    lst = list(lst)

반복할 횟수 count를 입력받는다.

count만큼 반복하여 괄호를 lst에 저장한다.

lst에는 문자열로 입력받았으나 이를 list로 바꾸어 원소를 하나씩 확인할 수 있도록 한다.

(아마 입력과 list typecasting을 한번에 할 수도 있을 것 같다.)

    for j in lst :
        if j == '(' :
            stack.append('(')
        elif j == ')' :
            if len(stack) != 0 and stack[-1] == '(' :
                stack.pop()
            else :
                stack.append(')')

입력받은 리스트를 반복문을 통해 확인한다.

만약 리스트의 원소가 '('라면 이를 스택에 추가한다. 이는 경우가 갈리지 않는다.

 

하지만 리스트의 원소가 ')'이라면

1. 스택이 비어 있지 않고, 스택의 마지막 원소가 '('라면 스택의 원소를 pop한다.

이는 '('과 ')'이 짝을 이루었기 때문에 더 이상 스택에 남아 있을 필요가 없기 때문이다.

 

2. 만약 스택이 비어 있거나 스택의 마지막 원소가 '('이 아니라면 스택에 ')'를 추가한다.

이는 스택이 비어 있을때 pop하면 에러가 나기 때문에 이미 짝이 맞지 않다는 것을 알려주기 위해 스택에 ')'를 추가하는 것이다.

위에서 스택의 마지막 원소가 '('인지 검사한 것과 같은 이치이다.

    if len(stack) == 0 : # VPS임
        print("YES")
    else : 
        print("NO")

스택이 무사히 다 짝을 찾아 pop되어서 남은 것이 없다면 VPS이기 때문에 YES를 출력한다.

그렇지 않다면 NO를 출력한다.

티스토리툴바