1. 문제 설명
[문제 내용]
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
-
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
-
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
-
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
-
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
-
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
[입력]
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.
[출력]
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
[입출력 예]
[힌트]
7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.
2. 풀이
import sys
while True:
sentence = sys.stdin.readline().rstrip()
if sentence == ".":
break
stack = []
balanced = True
brackets = {')': '(', ']': '['}
for char in sentence:
if char == '(' or char == '[':
stack.append(char)
elif char == ')' or char == ']':
if not stack or stack[-1] != brackets[char]:
balanced = False
break
stack.pop()
if balanced and not stack:
print("yes")
else:
print("no")3. 회고
3-1. 문제 풀이 과정
어떻게 풀어야 할지는 알겠는데 처리를 어떻게 할지 고민이 많이 되었던 문제이다. 힌트는 스택 구조를 이용해서 문제를 풀면 되는 것이었다. 자료 구조를 다시 한 번 복습하면 좋겠다는 생각이 들었다.
먼저 괄호 짝 딕셔너리를 먼저 생성해서 ( 또는 [가 들어왔을 때 ) 또는 ]가 서로 짝임을 인식할 수 있도록 한다. 자기 자신과 짝이 아닐 경우에는 계속 스택에 추가하고, 짝이 맞는 경우에는 스택에서 제거해 나간다.
스택 구조를 생각했으면 쉽게 접근할 수 있었는데 막상 떠오르지 않아서 어려웠던 것 같다. 문제 자체는 쉬운 편으로 느껴진다.
3-2. 새롭게 배운 내용
rstrip(): 문자열 끝에 있는 공백(스페이스)이나 특정 문자들을 제거하는 함수이다.sys.stdin.readline()을 사용하면 문장 끝에\n이 자동으로 포함되기 때문에rstrip()을 사용하여 삭제하고자 했다.
text = "hello world "
print(text.rstrip()) # "hello world" (오른쪽 공백 제거)특정 문자를 지정해서 해당 문자들을 제거할 수도 있다고 한다.
text = "Hello!!!"
print(text.rstrip("!")) # "Hello"