[백준/python] 4949번 : 균형잡힌 세상

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

 

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

 

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

 

정답

line = []
find = {')': '(', ']': '['}

line.append(input())
while line[-1] != ".":
    line.append(input())

for i in line[:-1:]:
    result = "yes"
    stack = []
    for n in i:
        if n in find.values():  # (, [ 가 들어올 때
            stack.append(n)
        elif n in find:  # ), ] 가 들어올 때
            if stack and stack[-1] == find[n]:  # stack의 마지막 값이 내 짝이라면
                stack.pop()
            else:
                result = "no"
                break
    if stack:   # stack에 ( 나 [가 있는 상태로 끝났을 때
        result = "no"
    print(result)

---

들어온 문장의 한글자씩 탐색해보면서 여는 괄호 (, [ 가 나오면 stack에 넣고

닫는 괄호 ), ] 가 나오면 stack.pop을 한 후 비교하는 방법이다.

 

find = {')': '(', ']': '['}

dictionary를 이용한 find에 괄호의 짝을 맞춰 저장해둔다.

키는 닫는 괄호로 하고 값은 여는 괄호로 한다.

 

for i in line[:-1:]:
    result = "yes"
    stack = []
    for n in i:

마지막에 들어오는 "."문장을 제외하고 각 문장의 글자를 하나씩 비교한다.

이때 최종적으로 구하고자하는 result값은 "yes"를 default로 설정하고 stack은 문장이 시작할 때 비워준다.

 

if n in find.values():  # (, [ 가 들어올 때
            stack.append(n)

글자가 여는 괄호 (나 [일 때, stack에 넣는다.

 

elif n in find:  # ), ] 가 들어올 때
            if stack and stack[-1] == find[n]:  # stack의 마지막 값이 내 짝이라면
                stack.pop()
            else:
                result = "no"
                break

글자가 닫는 괄호 ), ]일 때, 상황에 따라 다른 행동을 취해야한다.

만약 stack의 마지막 값이 find에 저장된 내 짝이라면 stack.pop()을 이용하여 stack에서 제거해준다.

이 외의 stack의 마지막 값이 내 짝이 아니거나 비어있을 때 등의 상황이라면 result을 "no"로 바꾸어준다.

이제 더이상 해당 문장의 글자를 확인할 필요가 없으므로 break를 이용하여 for문을 빠져나온다.

 

if stack:   # stack에 ( 나 [가 있는 상태로 끝났을 때
        result = "no"
    print(result)

해당 문장에 대한 결과 값 result를 출력해 주기 전, 짝을 맞추지 못한 괄호가 stack에 있는지 확인하고

stack에 값이 있다면 result를 "no"로 바꿔준 후 결과를 출력한다.