백준BOJ/Python : 4949번 균형잡힌 세상

4949번 : 균형잡힌 세상 원본

알고리즘 분류

• 자료 구조
• 문자열
• 스택

문제

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

풀이

무한 while문을 통해 열리는 소괄호와 대괄호에 대한 스택을 쌓으면서 소괄호 또는 대괄호가 닫히는 경우 pop()을 통해 적절한 소괄호 또는 대괄호가 반환되는 경우 true 그렇지 않으면 false로 처리하여 그에 따라 출력해주었다.

소스 코드

Python

while True:
    row = input()
    stack = []
    balance = True
    if row == ".":
        break
    for i in row:
        if i == "(":
            stack.append("(")
        elif i == ")":
            if len(stack) > 0:
                char = stack.pop()
                if char != "(":
                    balance = False
            else:
                balance = False
        elif i == "[":
            stack.append("[")
        elif i == "]":
            if len(stack) > 0:
                char = stack.pop()
                if char != "[":
                    balance = False
            else:
                balance = False
    if balance and len(stack) < 1:
        print("yes")
    else:
        print("no")