4949번 균형잡힌 세상

균형잡힌 세상

풀이

문자열 의 길이를 라 합시다.

스택을 이용하면 가 균형잡혔는지 에 판단할 수 있습니다.

문자열이 균형잡힐 조건은 아래와 같습니다.

어떤 괄호가 열리고 닫히는 사이에, 혹은 문자열 전체에서

1. 아직 열린 채 닫히지 않은 괄호가 있으면 안 됩니다.
2. 아직 열리지도 않은 괄호를 닫으려고 하면 안 됩니다.

마지막으로 열린 괄호의 종류를 기억하기 위해 스택을 사용합니다. 괄호가 닫히고 나면 스택에서 빼는 방식으로 그 이전에 마지막으로 열린 괄호를 확인할 수 있습니다.

알고리즘은 다음과 같습니다.

문자열의 맨 왼쪽부터 오른쪽까지 훑으면서

• 괄호가 아닌 경우 무시합니다.
• 여는 괄호인 경우 스택에 넣습니다.
• 닫는 괄호인 경우 스택의 top과 짝을 이루는지 검사합니다. 그렇지 않으면 아직 열리지도 않은 괄호를 닫으려고 하는 것이므로 는 균형잡힌 문자열이 아닙니다.
  만약 균형잡힌 문자열인 경우 스택의 top을 빼냅니다.

모든 문자를 훑고 나서 스택이 비어있지 않다면 열린 채 닫히지 않은 괄호가 존재한다는 뜻이므로 는 균형잡힌 문자열이 아닙니다.

코드

from collections import deque
 
 
def is_balanced(string: str) -> bool:
    matching = {")": "(", "]": "["}
 
    stack = deque()
 
    for char in string:
        if char == "(" or char == "[":
            stack.append(char)
        elif char == ")" or char == "]":
            if len(stack) == 0 or stack[-1] != matching[char]:
                return False
            stack.pop()
 
    if len(stack) > 0:
        return False
    return True
 
 
def main():
    while True:
        string = input()
 
        if string == ".":
            break
 
        if is_balanced(string):
            print("yes")
        else:
            print("no")
 
 
main()