백준 4949번 균형잡힌 세상 - Python

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

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

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

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

입력

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

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

출력

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

예제 입력 1

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

예제 출력 1

yes
yes
no
no
no
yes
yes

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

 

위 문제는 스택을 활용하는 문제였습니다.  괄호, 쌍과 관련된 문제라면 항상 스택을 활용하는 것이 아닐까? 생각해보는 것이 필요합니다. 이 문제는 당연하게도 스택의 개념을 이해하고 쓸 줄 안다면 금방 해결할 수 있는 문제였습니다. 다만, 위 문제에서 입력값은 별도의 문자(.)이 아닐 경우 무한정으로 입력을 받아서 연산을 진행한다는 것을 생각하고 문제를 풀어야 합니다.

while True:
    stack = []
    String = list(input())
    flag = True
    if len(String) == 1 and String[0] == '.':
        break

    for i in String:
        # print(i)
        if i == '(' or i == '[':
            stack.append(i)
        elif i == ')':
            if len(stack) > 0 and stack[-1] == '(':
                stack.pop()
            else:
                flag = False
                break
        elif i == ']':
            if len(stack) > 0 and stack[-1] == '[':
                stack.pop()
            else:
                flag = False
                break
        else:  # 일반 문자 또는 띄어쓰기 일 때
            pass

    if len(stack) != 0:
        flag = False

    if not flag:
        print('no')
    else:
        print('yes')

 

flag라는 별도의 변수를 두어서 [에 ]로 정상적인 쌍이 이루어지지 않을 경우, (에 정상적인 )로 쌍이 이루어지지 않을 경우, 스택에는 [나 (가 남아있는데 문장이 끝나버린 경우는 위 문제에서 말하는 균형이 잡힌 것이 아니기 때문에 flag가 False일 경우에는 'no' , True일 경우에는 'yes'를 출력하도록 했습니다. 처음에 이 문제를 풀면서 여러번 사소한 실수를 했었는데요.

1. no,yes를 No, Yes라고 대소문자를 헷갈려서 출력값의 결과가 일치하지 않아서 틀렸습니다.

2. 위 코드를 보시면 어떤 한 문장에서 ]또는 )를 만나게 될 경우에 stack의 TOP에 해당하는 [-1] 인덱스와 비교를 하는 조건문이 있습니다. 단, 스택에 1개라도 데이터가 존재해야지 비교를 할 수 있습니다. 위 조건을 elif len(stack) > 0 and i == ']로 위치를 의도하지 않은 다른 곳에 적는 실수를 하여 문제에 조건에 따른 분기가 잘못 되어졌습니다. 

문제는 쉬웠으나 잔 실수로 인해서 문제를 틀릴 수 있으니 내가 작성한 코드가 틀리다면, 사소한 실수는 없는지 확인해보는 것이 필요하겠습니다!