Python으로 푸는 백준 9012. 괄호

이 문제는 괄호 문자열이 쌍에 맞게 구성되어 있는지를 확인해서

'YES', 'NO'를 반환하도록 프로그램을 짜야한다.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 풀이

Stack을 이용하여 괄호 문자열이 쌍이 맞는지 확인한다.

문자열은 앞에서부터 순서대로 문자 하나씩 Stack에 넣는다. 

• Stack이 비어있는 경우에는 ')'는 들어갈 수 없다. ('NO' 반환)
• '('은 계속해서 쌓을 수 있다 (단, 모든 문자열을 확인했을때에는 Stack은 반드시 비어있어야 한다, 그렇지 않으면 'NO' 반환)
• ')'이 다음 차례로 들어갈 경우에는 ')'를 넣었다가 pop해줬다 치고 '(' 만 pop() 해준다.

위의 작업을 반복해 준다음, 모든 문자열을 확인하였을 때에 Stack이 비어있는지만 추가로 확인해주면 된다.

파이썬 코드

import sys
input = sys.stdin.readline
 
def solve(string):
 
    stack = []
    for ch in string:
 
        if len(stack) == 0 and ch == ')':
            return 'NO'
 
        if ch == '(':
            stack.append(ch)
        else:
            if stack[-1] == '(':
                stack.pop()
            else:
                return 'NO'
    if len(stack) == 0:
        return 'YES'
    return 'NO'
 
 
 
if __name__ == "__main__":
    n = int(input().strip())
    for i in range(n):
        string = input().strip()
        print(solve(string))