문제 링크

개요

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

문제 해설

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

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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')