[자료구조] 스택

Stack은 '쌓다', '무언가가 쌓여 있는 더미' 등을 의미한다. 스택은 의미 그대로 어떤 데이터를 삽입/삭제하는 과정을 '쌓는' 형태로 나타낼 수 있는 자료구조이다.

스택의 특징은 FILO (First In Last Out) 즉 먼저 저장된 데이터가 가장 나중에 나가는 방식으로 저장된다. 이름에서 힌트를 준것처럼 데이터가 차례대로 쌓인다. 가장 나중에 들어온 데이터는 먼저 나간다 LIFO (Last In First Out). 풜스트인풜스트 아웃 이말은 전에 TV 프로그램을 보다가 소방관 얘기가 나왔을 때 먼저 접했던 것 같다. 자료구조 얘기 하다가 뭔 소방관 얘기냐? 할 수 있겠는데 소방관들이 화재 현장을 들어 갈 때 FILO을 한다고 한다. 즉 먼저 들어가서 구조를 하고 끝까지 현장에 남아서 구조를 요청하는 자가 있는지 살핀다음 제일 마지막으로 나오는 것이다. 진짜 존경합니다 소방관분들...

홈페이지 방문하고 뒤로가기 버튼을 누를때 바로 이전페이지가 나오는데 이게 바로 스택 구조를 사용한 것이다. 즉 방문 페이지가 순서대로 스택에 삽입/삭제되는 것이다.

스택의 데이터를 넣고 뺄 때 시간 복잡도는 O(1)이므로 만약 N개의 데이터를 넣고 빼야 한다면 총 O(N)이 될 것이다.

 

문제

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

 

예제 입력

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

예제 출력

NO
NO
YES
NO
YES
NO

 

문제 풀이

문자열을 순차적으로 보면서 여는 괄호가 들어오면 스택에 넣고, 닫는 괄호가 들어오면 스택의 top과 비교해서 종류가 맞으면 스택에서 pop한다. 종류가 맞지 않거나 스택이 비어 있다면 올바른 괄호 문자열(VPS)이 아니다. 

위 과정을 반복해서 최종적으로 스택이 비어 있으면 여는 괄호가 전부 짝이 맺어졌다는 뜻이므로 올바른 괄호 문자열(VPS)이다. 비어 있지 않다면 여는 괄호가 더 많이 들어 왔다는 의미이므로 올바른 괄호 문자열(VPS)이 아니다. 

import sys
input = sys.stdin.readline

for i in range(int(input())):
    stk = [] # 괄호 담을 스택
    ans = "YES" # 대답 설정
    for f in input().rstrip(): # 인풋 낱개 하나하나
        if f == "(":
            stk.append(f) # 하나씩 담기
        else:
            if len(stk) > 0:
                stk.pop() # )가 입력된는 상황이다. 만약 (가 있다면 (를 뺀다
            else:
                ans = "NO" # )가 입력될때 (가 없다면 대답은 노
    if len(stk) > 0:
        ans = "NO" # 최종적으로 봤을때 남아있는 ( ) 둘 중 하나라도 남아있다면 노
    
    print(ans)