문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
입력
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
내 풀이
while True:
str1 = input()
if str1==".":
break
list1 = []
for s in str1:
if s == "(" or s == "[":
list1.append(s)
elif s == ")":
if len(list1)!=0 and list1[-1]=="(":
list1.pop()
else:
list1.append(s)
elif s == "]":
if len(list1)!=0 and list1[-1]=="[":
list1.pop()
else:
list1.append(s)
if len(list1)==0:
print('yes')
else:
print('no')코멘트
문제를 보자마자 백준 9012번 괄호 문제가 생각나면서 스택을 이용해 괄호의 짝이 맞으면 pop해서 삭제하는 식으로 풀어야 겠다는 생각이 들었다. 하지만 괄호의 종류가 2개이고, 무엇보다 단순히 두 괄호 쌍이 짝이 맞는 것 뿐만 아니라 순서에도 주의를 해야 했다.
이는 예제 입력 1의 Help( I[m being held prisoner in a fortune cookie factory)]. 에서 볼 수 있는데, ( 다음으로 [ 가 열렸으니 ] 로 먼저 닫고 마지막에 ) 로 닫아야 하는데, )가 먼저 닫혔으니 no라는 결과가 출력되는 것에 주의해야 한다.
이는 위의 코드에서처럼 마지막으로 열린 것이 (list1[-1]) ( 인지 [ 인지를 확인해서 짝이 맞다면 pop 하고 아니면 append해서 list1에 남아있는 괄호가 없다면 균형이 잡혀 있는 것으로 판단해서 yes를 출력하도록 하면 된다.
문제에서 "문자열도 균형이 잡혀야 한다"라는 것이 무슨 의미인지는 아직 모르겠는데 딱히 신경 쓸 필요가 없는 문구인 것 같다.
⚠ 문자열 문제에서는 import sys, input = sys.stdin.readline을 사용하지 말자. 개행 문자 \n 이 포함되어 출력 초과가 뜬다.
References
https://www.acmicpc.net/problem/4949
https://velog.io/@kupulau/%EB%B0%B1%EC%A4%80-9012-%EA%B4%84%ED%98%B8