https://www.acmicpc.net/problem/4949
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
# 백준 4949번 : 균형 잡힌 세상
# tip)
# 괄호가 (] 또는 [)로 묶이는 것도 균형 잡히지 않은 것이기 때문에 고려해야 함
def solution(i):
stack = []
for j in list(i):
if j == '(' or j == '[': # 여는 괄호인 경우 stack에 추가
stack.append(j)
elif j == ')': # 닫힘 소괄호이면, stack 안에 아무 것도 들어있지 않거나 [ 로 열려있는 상태일 경우 불균형이라고 판단
if len(stack) == 0 or stack[-1] != '(':
return 'no'
else:
stack.pop()
elif j == ']':
if len(stack) == 0 or stack[-1] != '[': # 닫힘 대괄호이면, stack 안에 아무 것도 들어있지 않거나 ( 로 열려있는 상태일 경우 불균형이라고 판단
return 'no'
else:
stack.pop()
if len(stack) == 0: # stack에 대한 모든 연산 후, 스택이 다 비워지면 균형잡힌 상태
return 'yes'
else: # stack 안에 기호가 남아있는 경우 불균형 상태
return 'no'
input_str = []
while True:
s = str(input()) # 입력 받은 문장
if s == '.':
break
else:
input_str.append(s)
for i in input_str:
print(solution(i))
💡 마지막에 한 가지 케이스를 고려하지 못해 오류가 났었다. 괄호가 동일한 종류의 쌍으로 마무리되지 않는 경우이다.
예) ( ]으로 닫히거나, [ )으로 닫히는 경우를 고려하지 못했다.
해당 부분으로 고려하는 데 위의 링크를 참고했다.