[Python] 백준4949번 : 균형잡인 세상

💡문제

백준 4949번 문제 링크

🍀풀이

코드

import sys
input = sys.stdin.readline

while True:
    command = input().rstrip()
    stack = []

    if command == '.':
        break
    
    for i in command:
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ')':
            if len(stack) != 0 and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(i)
        elif i == ']':
            if len(stack) != 0 and stack[-1] == '[':
                stack.pop()
            else:
                stack.append(i)
                
    if len(stack) == 0:
        print('yes')
    else:
        print('no')

이런 괄호 쌍 문제는 배열로 풀면 O(N2), 연결리스트는 O(N)이라고 한다. 그치만 스택으로 풀면 더 간단하게 풀 수 있다고 함! 파이썬에서 스택은 list로 구현!

• 괄호의 종류가 1개이면 여는 괄호의 갯수와 닫는 괄호의 갯수로 비교하면 됨
• 괄호의 종류가 여러개면, 불가능하기 때문에 쌍 비교를 하면 됨

그래서 일단 여는 괄호는 다 스택에 넣어주고, 닫는 괄호가 나오면 스택에 제일 최근에 담긴 값과 비교해서 같은 쌍이면 pop()하고 아니면 append()하면 된다.