[백준 4949] 균형잡힌 세상 (Python)

2022. 3. 22. 22:42

문제 링크 #

https://www.acmicpc.net/problem/4949

개요 #

스택을 이용하여 풀 수 있는 문제이다.
문자열 처리에 관한 능력이 추가로 요구된다.
최대 입력 크기가 정해지지 않았기에 시간 복잡도는 무시한다.

문제 해설 #

해당 문제에서 고려해야할 문자는 종료 조건인 점(’.’)을 제외하면 소괄호와 대괄호 뿐이다.
균형잡힌 문장의 구분 여부는 1. 닫힌 괄호가 열린 괄호보다 앞에 나온 경우 2. 열린 괄호가 안 닫힌 경우로 판단했다.
문자 하나하나마다 확인하며 괄호를 골라낼 수도 있지만 이번엔 정규식을 사용해본다.
우선 정규식 라이브러리인 re에 속한 sub 메서드를 사용해 괄호를 제외한 모든 문자를 제거한다.
나머지 문자에 대해 for문을 돌려 열린 괄호면 스택에 추가, 닫힌 괄호면 스택에 남은 값을 뺀다.
단, 닫힌 괄호의 경우 스택에 열린 괄호가 없거나 스택 맨 위의 값이 다른 종류의 괄호면 균형이 깨졌다 판단한다.
코드의 중복을 발생시키지 않기 위해 균형이 깨진 경우를 IndexError의 발생으로 통일하고
이 때 조건 변수를 재설정하고 반복문을 중지시킨다.
반복문이 종료된 후 스택과 조건 변수에 대한 NAND 결과를 통해 균형잡힌 문장의 여부를 판단하여 결과를 출력한다.

해설 코드 #

python

import re

match = {')': '(', ']': '['}

while True:
    balanced_stack = []
    unbalanced = False
    sentence = input()
    if sentence == '.':
        break

    sentence = re.sub('[^\(\)\[\]]+', '', sentence)
    for bracket in sentence:
        if bracket in {'(', '['}:
            balanced_stack.append(bracket)
        else:
            try:
                if balanced_stack[-1] == match[bracket]:
                    balanced_stack.pop()
                else:
                    raise IndexError
            except IndexError:
                unbalanced = True
                break
    
    if not(balanced_stack or unbalanced):
        print('yes')
    else:
        print('no')