4949_균형잡힌 세상 ...반례?

문제는 더보기!

 

균형잡힌 세상 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

49843

16453

13029

32.496%

문제

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

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

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

 

 

 

저번글에서 풀었던 괄호 문제와 상당히 유사하다. 이번엔 괄호가 2개인 점이 다르다.

 

역시 스택구조를 사용하면 구현할 수 있다.

들어오는 문자가 ( 이거나 [ 이면 리스트에 추가하고

 

) 가들어왔는데 스택의 마지막이 (가 아니거나

] 가 들어왔는데 스택의 마지막이 [가 아닌 경우엔 for문을 아예 끝내버리면 되고 아니면 짝지어 들어있던 

 

(나 [ 를 pop 해주면 된다.

 

string=input()
while(string != '.'):
    lst = []

    for i in string:
        if i =='(' or i =='[':
            lst.append(i)
        elif i==')':
            if '(' not in lst:
                lst.append(i)
                break
            elif lst[-1] !='(':
                break
            else:
                lst.pop()
        elif i==']':
            if '[' not in lst:
                lst.append(i)
                break
            elif lst[-1] != '[':
                break
            else:
                lst.pop()


    print('yes' if len(lst) == 0 else 'no')
    string = input()

 

 

문제풀다 어이없는 반례때문에 시간을 잡아먹었는데

 

yes or no 로 답해야하는데 YES NO 로 출력하는 바람에 출력이 되지 않았다....

 

문제조건을 역시 잘봐야 한다.