균형잡힌 세상

solved_ac[Class2][균형잡힌 세상](https://www.acmicpc.net/problem/4949)

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

예제 출력 1

yes
yes
no
no
no
yes
yes

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

문제 해석

소괄호 "("이 하나 나오면 무조건 소괄호의 쌍인 ")"이 나와야한다. 대괄호도 마찬가지다. 예를 들면 (안녕 [나는] 동혁이야). 이 나오면 균형을 이루는 것이기 때문에 출력으로는 yes가 나와야 한다. 하지만 (안녕 [나는) 동혁이야]. 가 나온다면 균형을 이루지 못하기 때문에 no가 나오는 것이다. 시작이 되는 문자인 (과 [이 나왔을때 가장 마지막에 나온것이 가장 먼저 닫혀야 하는 것이기 때문에 같은 원리인 stack 알고리즘이 쓰여야 한다.

stack

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

그림에서 보는 것처럼 스택에서의 입출력은 맨 위에서만 일어난다.

• 입출력이 이루어지는 부분 : 스택 상단 (stack top)
• 반대쪽인 바닥 부분 : 스택 하단 (stack bottom)
• 스택에 저장되는 것 : 요소 (element)
• 요소가 하나도 없는 스택 : 공백 스택 (empty stack)
• 반대로 스택이 요소로 꽉 차있을 경우 포화 상태 (full)

시간 복잡도

• push : 삽입 연산 O(1)

  • 스택이 포화 상태인지 확인 후 연산

• pop : 삭제 연산 O(1)

  • 스택이 공백 상태인지 확인 후 연산

• peek : top 요소 반환 (삭제 x)

  • 스택이 공백 상태인지 확인 후 연산

• 특정 데이터 검색 O(n)

풀이

• 마지막 문자인 "." 이 들어온다면 입력을 더이상 받지 않기 때문에 무한 루프에서 break 지점으로 설정해준다. . 다음에 개행이 된 문자가 입력이 되기 때문에 .\n 으로 비교해준다.

• 입력 받은 문자열의 크기만큼 루프를 돌면서 "("과 "["를 찾는다.

  • 만약 찾았으면 앞에서 초기화 해준 stack_list에 넣어준다.

• ")"과 "]"을 찾는다

  • 만약 예를 들어 ")"를 찾았다면 stack이 비어있는지 확인하고 비어있다면 no를 출력하고 stack을 clear 함수를 써서 초기화 해주고 for문을 빠져나온다. 만약 비어있지는 않은데 stack의 가장 끝 문자가 "("이 아니면 균형을 이루지 못하였기 때문에 위와 똑같이 no를 출력한 후 stack을 clear 함수를 써서 초기화 해주고 for문을 빠져나온다. "]"도 마찬가지이다.
  • 만약 비어 있지 않으며 짝이 맞는 문자를 찾았다면 짝이 맞는 문자를 pop 함수를 이용해 삭제해주고 다시 for 문을 돈다.

• 문자열의 길이만큼 for문을 다 돌았다면?

  • stack이 비어 있으면 해당되는 문자들이 균형을 이루었거나 아예 나오지 않은 것이기 때문에 yes를 출력해준다.
  • 비어 있지 않으면 균형을 이루지 못한 것이기 때문에 no를 출력해주고 다시 다른 입력 받은 문자열을 검사해야 하기 때문에 비어있지 않은 stack을 초기화 해준다.

import sys
stack_list = []
while True:
    str_input = sys.stdin.readline()
    if str_input == ".\n":
        break
    for i in range(len(str_input)):
        if str_input[i] == "(":
            stack_list.append("(")
        elif str_input[i] == "[":
            stack_list.append("[")
            
        elif str_input[i] == ")":
            if not stack_list or stack_list[-1] != "(":
                print("no")
                stack_list.clear()
                break
            else:
                stack_list.pop()
        elif str_input[i] == "]":
            if not stack_list or stack_list[-1] != "[":
                print("no")
                stack_list.clear()
                break
            else:
                stack_list.pop()
            
        elif i == len(str_input) - 1:
            if not stack_list:
                print("yes")
            else:
                print("no")
                stack_list.clear()

고찰

여러개의 문자열을 입력 받는데 처음에는 2차원 배열을 생각하였다. 하지만 얼마나 입력 받을지도 모르는 상황에서 메모리를 낭비할 수 없기 때문에 while문 한번 돌 때마다 바로 검사를 하였다. 그렇게 되니 stack을 쓰는데 끝나고 나면 초기화를 해줘야 하는 상황이 있었다. 초기화를 하지 않아서 계속 틀리게 되어서 시간을 많이 사용하였는데 어떤 문제를 풀던지 다시 재사용 되는 배열이나 자료구조에 대해서는 초기화가 필수라는 것을 깨달았다.