저별이의 초보 코딩

https://www.acmicpc.net/problem/4949

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)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

yes
yes
no
no
no
yes
yes

이 문제가 처음에는 쉬워 보일 수 있지만 '균형잡힌 문자열'이라는 단어에 주목해야 한다.

나 역시도 단계별 문제에서 앞 문제였던 '괄호' 문제와 같은 방식으로 풀다가 균형잡힌 이라는 말때문에 막혔다.

어떤 과정으로 균형을 잡힌 것을 찾아내는 것일까?

여기서 원하는 것은 열리는 게 ([이라고 한다면 ])가 되어야 한다는 것이다. 만약 비어있는 상태나 ( [ ( ]로 형태가 맞지 않는다면 false로 받아야 한다.  

while(1):
    line=input()
    line_1=list(line)#이건 오류 방지용 리스트따로
    stack=[]
    temp=True

    if(line=='.'):#종료조건 만족시
        break
    for i in line_1:
        if(i=='(' or i=='['):
            stack.append(i)
        elif(i==')'):
            if not stack or stack[-1]=='[':
                temp=False
                break
            elif stack[-1]=='(':
                stack.pop()
        elif(i==']'):
            if not stack or stack[-1]=='(':
                temp=False
                break
            elif stack[-1]=='[':
                stack.pop()
    if temp==True and not stack:
        print("yes")
    else:
        print("no")
    #print(line)

일단 입력받는 과정은 크게 다르지 않다. input으로 입력받아 리스트로 바꿔준다.

그리고 while문 탈출은 바로 문자열에 '.'이 있는지만 확인해주고 break으로 탈출을 시키면 된다.

문제는 for문을 돌릴때인데

일단 여는 소괄호, 대괄호는 stack에 쌓아준다.

그리고 닫힐 때는 앞에 소괄호 혹은 대괄호가 있는지 확인을 해주어야 한다.

만약 닫아주어야 하는 형태 앞에 균형이 맞지 않으면 no로 출력을 해주어야 한다.

하지만 닫아주어야 하는 형태인데 같은 기호이지만 열리는 것이라면 뽑아주어야 한다.

뽑아주어야 하는 이유는 성립했기 때문이다. ()나 []형태로 만들어졌기 때문에 비워주어야 한다. false라면 stack에 기호가 남아있을 것이다.

stack이 아니라는 것은 리스트가 empty라는 말이다.

이렇게 stack이라는 리스트에 열리는 것이라면 닫는 것을 맞춰주어야 하고 안에서는 무조건 균형을 맞추어 닫아주어야 한다. 이것을 생각하는 과정이 굉장히 어려웠던 것 같다.