[백준 9012번] 파이썬 - 괄호

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

9012번: 괄호

 

# 조건

• VPS를 판별하는 문제이다.
• VPS란, 괄호가 짝이 맞는 경우를 말하는데, (())와 같이 괄호안에 올바른 괄호가 들어가 있는 경우도 포함이다.
• 첫 째줄에는 테스트 케이스 수 N, 그 이후에는 괄호 문자열이 주어진다

 

# 접근 방법 및 SOLUTION

• 전형적인 STACK문제라고 생각이 들었다.
• 여는 괄호가 온다면 괄호 리스트에서 POP과 동시에 STACK에 넣어준다.
• 닫는 괄호라면 괄호 리스트에서 POP을 해주며, STACK이 존재한다면! (비어있는 경우를 생각해서) POP을 해준다.
• STACK이 비어있는데 닫는 괄호가 들어온다면 VPS가 아니므로 RETURN 'NO'
• 괄호 리스트에서 모든 괄호를 꺼냈을 때, 스택에 원소가 있다면 VPS아니므로 RETURN 'NO'
• 스택이 비었다면 RETURN 'YES'

 

# 괄호 리스트를 받아준 후
def vps(gwalho):  
	# 리스트가 )로 시작한다면 올바르지 않으므로 NO 반환
    if gwalho[0] == ')':  
        return 'NO'  
    else:  
    	# gwalho pop(0)해주며 스택에 append
        # 위에서 닫는괄호 걸러줬으므로 무조건 여는 괄호
        stack = [gwalho.pop(0)]
        # 괄호 리스트가 존재하는 동안 반복
        while gwalho:  
        	# 여는 괄호가 들어온다면
            if gwalho[0] == '(':
            	# gwalho pop해주며 스택에 append
                stack.append(gwalho.pop(0))  
            # 닫는 괄호의 차례라면
            elif gwalho[0] == ')':
            	# 괄호 pop
                gwalho.pop(0)
                # 스택에 '(' 가 있어야 하므로, 존재할 때만 pop
                # 스택이 비어있다면 vps가 아니므로 'no' return
                if stack:  
                    stack.pop(0)  
                else:  
                    return 'NO'  
        # 괄호 문자열을 다 받아준 후 스택이 비어있지 않다면 vps가 아니다
        if stack:  
            return 'NO'  
        else:  
            return 'YES'  
  
  
  
N = int(input())  
for i in range(N):  
    gwalho = list(input())  
    print(vps(gwalho))