[BOJ/Python] 4949 : 균형잡힌 세상

👉 문제 링크

👉 첫번째 시도 (❌틀린코드❌)

while True:
    s = input()
    stk = []

    cnt1, cnt2 = 0,0

    if s == '.':
        break

    for i in s:
        if i == '[':
            cnt1 += 1

        elif i == '(':
            cnt2 += 1

        elif i == ']':
            cnt1 -= 1
        
        elif i == ')':
            cnt2 -= 1

        if cnt1 < 0 or cnt2 < 0:
            break 
    
    if cnt1 == 0 and cnt2 == 0:
        print('yes')
    else:
        print('no')

[, ], (, ) 의 횟수를 각각 세는 방법을 처음 시도했다.

이 방법이 틀린 이유는,
"짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다."
이 조건 때문이다.

예를 들어,
[ 안녕하세요. ) ]
이 문장은 대괄호 사이 문자열이 균형 잡혔다고 할 수 없다.

위 코드는 이 조건을 무시하는 코드였다.
닫히기만 하면 되는 줄 알았지만 가장 최근에 열린 괄호부터 닫혀야 한다 !

👉 두번째 시도

while True:
    s = input()

    stk = []

    if s == '.':
        break

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

두번째로 생각했던 방법은
스택에 열린 괄호를 넣고 마지막에 들어온 괄호와 닫힌 괄호와 짝을 이루는지 확인하는 방법이다.
괄호가 짝을 이루면 스택에서 제거, 아닌 경우에는 닫힌 괄호를 스택에 넣는다.