[Python] [백준] 4949번 - 균형잡힌 세상 (stack 사용)

균형잡힌 세상  

1 초

128 MB

74917

24843

19564

32.370%

문제

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

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

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 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

---

딱 봐도 스택으로 푸는 문제인 것이 이제는 보인다.

 

생각의 흐름은 다음과 같다.

1. (, [, ], ), . 이 아닌 알파벳들은 무시하고 괄호와 점만 보고 해결한다.

2. (, [ 은 쌓아주고 ), ] 가 들어오면 이전에 쌓아논 (, [ 를 내보낸다.

3. . 이 들어오면 내부 반복문을 멈춘다.

4. stack의 길이가 1인데 . 만 들어있다면 균형잡혔으므로 yes, 아니면 no

 

--> 그럴듯 하지만 바로 틀림....

 

1. 틀린코드

import sys

# 문자열 주어짐
while True:
    stack = []
    input_data = sys.stdin.readline().rstrip()
    if input_data == '.':
        break
    for character in input_data:
        if character == '(':
            stack.append(character)
        elif character == '[':
            stack.append(character)
        elif character == ')' and '(' in stack:
            stack.pop()
        elif character == ']' and '[' in stack:
            stack.pop()
        elif character == '.':
            stack.append('.')
            break
    if len(stack) == 1 and stack[0] == '.':
        print('yes')
    else:
        print('no')

---

2. 20% 맞은 코드

import sys

# 문자열 주어짐
while True:
    stack = []
    input_data = sys.stdin.readline().rstrip()
    if input_data == '.':
        break
    for character in input_data:
        if character == '(':
            stack.append(character)
        elif character == '[':
            stack.append(character)
        elif character == ')':
            if '(' in stack:
                stack.pop()
            else:
                stack.append(character)
        elif character == ']':
            if '[' in stack:
                stack.pop()
            else:
                stack.append(character)
        elif character == '.':
            stack.append(character)
            break
    if len(stack) == 1 and stack[0] == '.':
        print('yes')
    else:
        print('no')

), ] 가 들어왔지만 pop할 (, [ 가 없다면 stack에 ), ] 를 쌓아둔다.

그럼 출력할 때 len(stack) 이 1이 아니므로 no가 출력된다.

하지만 어떤 테스트케이스에서 막혀서 틀렸다...

 

 

---

3. 맞은 코드

import sys

# 문자열 주어짐
while True:
    stack = []
    input_data = sys.stdin.readline().rstrip()
    flag = True
    if input_data == '.':
        break
    for character in input_data:
        if character == '(' or character == '[':
            stack.append(character)
        elif character == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                flag = False
                break
        elif character == ']':
            if stack and stack[-1] == '[':
                stack.pop()
            else:
                flag = False
                break
    print('yes' if flag and not(stack) else 'no')

 

flag = True

: 균형잡힌 세상이 아니라면 바로 종료하고 no를 출력하기 위해 상태값을 나타낼 변수를 만듦.

 

if input_data == '.':
    break

: . 만 입력되면 while문은 바로 멈춤

 

elif character == ')':
    if stack and stack[-1] == '(':
        stack.pop()
    else:
        flag = False
        break

: 위의 틀린 코드들과의 가장 큰 차이점이다.

if stack은 stack안에 값이 있으면 True, 비어있으면 False를 반환한다.

따라서 ) 가 들어왔을 때, stack이 비어있지 않고, 마지막에 쌓였던 것이 ( 라면 pop()한다는 뜻이다.

 

그럼 stack[-1]이면 마지막에 쌓여있는 것을 보는 건데,

마지막에 쌓인 게 ( 나 [ 가 아니라면 무조건 균형이 무너진 걸까?

 

그렇다.

닫는 기호마다 열린기호가 빠져 나가면서 균형을 확인하는데

) 가 들어왔을 때 바로 앞에 ( 가 아니라면

] 가 들어왔을 때 바로 앞에 [ 가 아니라면

균형이 이미 무너진 것이다.

 

) 가 들어올 때마다 ( 랑 같이 빠져나가서

균형잡인 문자열이라면 이전의 ) 는 있을 수 없다.

 

만약 ) 가 들어왔을 때

마지막에 ) 가 있는 경우, [ 가 있는 경우, ] 가 있는 경우를 본다면

균형이 맞지 않아서 남아있는 것이다. 

 

그래서 이런 경우에는

상태값을 False로 바꿔주고

for문을 빠져나오는 break문을 사용한다.

 

++ 추가로 . 이 들어오는 것을 무시해도 되는 이유는

. 만 들어오는 경우는 flag가 True로 유지되고,

stack에는 어떤 값도 append() 되지 않기 때문에

아래에서 출력할 때 yes가 나오기 때문이다.

 

 

print('yes' if flag and not(stack) else 'no')

: 마지막엔 삼항연산자를 통해 출력한다.

flag가 True 이면서 stack에 어떤 괄호문자도 없이 비어있다면 yes를 출력하고

아니라면 no를 출력하라.

 

시간복잡도는 입력받은 문자열의 길이만큼의 시간이 걸린다.

O(N)