[백준 4949] 균형잡힌 세상 (Python)
문제 링크 #
개요 #
- 스택을 이용하여 풀 수 있는 문제이다.
- 문자열 처리에 관한 능력이 추가로 요구된다.
- 최대 입력 크기가 정해지지 않았기에 시간 복잡도는 무시한다.
문제 해설 #
- 해당 문제에서 고려해야할 문자는 종료 조건인 점(’.’)을 제외하면 소괄호와 대괄호 뿐이다.
- 균형잡힌 문장의 구분 여부는 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')