[파이썬] 단계별 백준 문제 풀기 - 4949 스택 (균형잡힌 세상)

문제

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

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

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

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

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

입력

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

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

출력

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

 

---

<<소스코드>>

while True: #참일때 반복
    words = input()
    stack = []
    if words == '.': #'.'을 만나면 break로 종료 
        break
    for i in words: #만약 input된 값이 열린 괄호라면 stack에 추가한다.
        if i == '[' or i =='(':
            stack.append(i)
        elif i == ']': #만약 닫힌 괄호 중 ']' 라면, 
            if len(stack) !=0 and stack[-1] ==  '[': #스택이 비어있지 않고, 스택의 마지막값(직전에 넣은 값)이 열린 괄호라면
                stack.pop() #스택에서 빼주기! (스택에서 탈출, yes!)
            else: #만약 스택이 비었거나, 마지막값이 '['가 아니라면
                print('no') #불완전한 문장이므로 no 출력하고 break로 탈출
                break
        elif i == ')': #만약 닫힌 괄호 중 ')' 라면,
            if len(stack) !=0 and stack[-1] == '(': #스택이 비어있지 않고, 스택의 마지막에 들어온 값이 '(' 이라면
                stack.pop() #스택에서 탈출!!! 빼주기
            else: #그게 아니라면 불완전한 문장이니까 no 출력하고 break로 탈출
                print('no')
                break
    else: #문장이 .으로 끝나는게 아니면서,
        if len(stack) == 0: #스택의 길이가 0이면, 문제없을 경우 완전한 문장이므로 yes 출력 
            print('yes')
        else: #스택의 길이가 0이 아니면, 짝없는 무언가가 빠져나오지 못하고 남은게 있는것이므로 no 출력 
            print('no')

 

<<결과값>>

 

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

---

아 진짜 오래걸렸다ㅠㅠ 처음에 메모리초과가 나왔다.

그 다음에는 A rope may form )( a trail in a maze가 yes로 나왔다.

엉망진창 코드 (｡•́︿•̀｡)....

 

이 문제는 스택을 이용해서 풀어야한다. 스택은 가장 나중에 넣은 글자가 가장 먼저 나온다! 

즉 괄호는 짝이 맞아야하므로 스택에 제일 최근에 들어온 괄호가 열린 괄호일 때, 짝이 맞는 닫힌 괄호가 그 다음에 발견되면, 스택에서 빼준다. ( 스택에서 빼준다. 스택에는 불완전한 괄호만 남거나 비게 된다) 

 

while문은 break 조건을 잘못주거나 라인을 제대로 안맞출 경우, 무한루프가 돌 수 있다... 나는 무한루프때문에 시간초과가 나왔었다. 조심해야겠다.

 

 

- stack() : 스택은 먼저 들어간 항목이 나중에 나오고, 나중에 들어간 항목이 먼저 나오는 Last In First Out  구조이다.   즉 출입구가 하나밖에 없어 요소가 쌓이게 되면 맨 위부터 꺼내야한다!! 

 

- [stack]의 메소드  

   push() 맨 앞에 데이터 넣기

   pop() 맨 앞에 데이터 뽑기

   peek() 맨 앞에 데이터 보기

   isEmpty() 스택이 비었는지 안 비었는지 여부 반환해주기 (True/False)