BOJ 9012. 괄호

륵기 2020. 5. 8. 17:43

728x90

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

9012번: 괄호

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

www.acmicpc.net

# 테스트케이스 수 입력
t = int(input())

for _ in range(t):
    #괄호 입력 리스트 생성
    inp = list(input())
    
    #리스트 길이가 0이 될때까지
    while len(inp) != 0:
    
    #첫괄호가 ) 이거나 마지막 원소 괄호가 ( 면 괄호 생성 불가
        if inp[-1] == '(' or inp[0] ==')':
            print('NO')
            break
    # ( 와 ) 가 둘다 리스트에 존재시에 순서대로 제거 '()'의 형태로 제거
        if '(' and ')' in inp:
            inp.remove('(')
            inp.remove(')')
        else:
            print('NO')
            break
            
    #최종적으로 길이가 0이 되면 괄호 완성이 되는 것임
    if len(inp) == 0:
        print('YES')

t = int(input())
for _ in range(t):
    inp = list(input())
    close_cnt = 0
        
    while(len(inp) != 0):
    	# 카운트가 0보다 작아지면 괄호 불가능 -> 스택에서 처음으로 '('를 pop하게 되면
 		# 괄호 생성 불가하다는 것과 같은 원리
 		if(close_cnt < 0):
            break
        # 원소 pop
        res = inp.pop()
		
        # 원소 카운트 계산
        if(res == '('):
            close_cnt -= 1
        elif(res == ')'):
            close_cnt += 1
            
    if(close_cnt == 0):
        print('YES')
    else:
        print('NO')

728x90