백준 온라인 저지, 자료구조 / 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번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

W3sicHJvYmxlbV9pZCI6IjQ5NDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZTBcdWQ2MTVcdWM3YTFcdWQ3OGMgXHVjMTM4XHVjMGMxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzhcdWFjYzRcdWIyOTQgXHVhZGUwXHVkNjE1XHVjNzc0IFx1Yzc5OCBcdWM3YTFcdWQ2MDBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM1OTFcdWFjZmMgXHVjNzRjLCBcdWJlNWJcdWFjZmMgXHVjNWI0XHViNDYwIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM2N2NcdWNhYmQgXHVhZDA0XHVkNjM4XHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkMDRcdWQ2MzhcdWNjOThcdWI3ZmMgXHViOWQwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWJiZmNcdWM3NzRcdWM3NTggXHVjNzg0XHViYjM0XHViMjk0IFx1YzViNFx1YjVhNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZDA0XHVkNjM4XHViNGU0XHVjNzU4IFx1YWRlMFx1ZDYxNVx1Yzc3NCBcdWM3OTggXHViOWRlXHVjZGIwXHVjODM4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWQzMTBcdWIyZThcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YzlkY1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVhZDA0XHVkNjM4XHViMjk0IFx1YzE4Y1x1YWQwNFx1ZDYzOCgmcXVvdDsoKSZxdW90OykgXHVjNjQwIFx1YjMwMFx1YWQwNFx1ZDYzOCgmcXVvdDtbXSZxdW90OylcdWI4NWMgMlx1Yzg4NVx1Yjk1OFx1Yzc3NFx1YWNlMCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YWRlMFx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjODcwXHVhYzc0XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YzY3Y1x1Y2FiZCBcdWMxOGNcdWFkMDRcdWQ2MzgoJnF1b3Q7KCZxdW90OylcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzE4Y1x1YWQwNFx1ZDYzOCgmcXVvdDspJnF1b3Q7KVx1YzY0MFx1YjljYyBcdWM5ZGRcdWM3NDQgXHVjNzc0XHViOTA0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YzY3Y1x1Y2FiZCBcdWIzMDBcdWFkMDRcdWQ2MzgoJnF1b3Q7WyZxdW90OylcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjMwMFx1YWQwNFx1ZDYzOCgmcXVvdDtdJnF1b3Q7KVx1YzY0MFx1YjljYyBcdWM5ZGRcdWM3NDQgXHVjNzc0XHViOTA0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkMDRcdWQ2MzhcdWI0ZTRcdWM3NDAgXHVjNzkwXHVjMmUwXHVhY2ZjIFx1YzlkZFx1Yzc0NCBcdWM3NzRcdWI4ZjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2N2NcdWNhYmQgXHVhZDA0XHVkNjM4XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YWQwNFx1ZDYzOFx1YjRlNFx1Yzc1OCBcdWM5ZGRcdWM3NDAgMToxIFx1YjllNFx1Y2U2ZFx1YjljYyBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1Yzk4OSwgXHVhZDA0XHVkNjM4IFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWI0NTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWQwNFx1ZDYzOFx1YzY0MCBcdWM5ZGRcdWM5YzBcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM5ZGRcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YjQ1MCBcdWFkMDRcdWQ2MzhcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHViM2M0IFx1YWRlMFx1ZDYxNVx1Yzc3NCBcdWM3YTFcdWQ2MDBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzgxNVx1YmJmY1x1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVhZGUwXHVkNjE1XHVjN2ExXHVkNzhjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3OFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzBcdWI5N2MgXHVkMzEwXHViMmU4XHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkNTU4XHViMDk4IFx1YjYxMFx1YjI5NCBcdWM1ZWNcdWI3ZWNcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNjAxXHViYjM4IFx1YzU0Y1x1ZDMwY1x1YmNiMywgXHVhY2Y1XHViYzMxLCBcdWMxOGNcdWFkMDRcdWQ2MzgoJnF1b3Q7KCApJnF1b3Q7KSBcdWIzMDBcdWFkMDRcdWQ2MzgoJnF1b3Q7WyBdJnF1b3Q7KVx1YjRmMVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwXHVhZTAwXHVjNzkwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxkaXY+XHVjNzg1XHViODI1XHVjNzU4IFx1Yzg4NVx1YjhjY1x1Yzg3MFx1YWM3NFx1YzczY1x1Yjg1YyBcdWI5ZTggXHViOWM4XHVjOWMwXHViOWM5XHVjNWQwIFx1YzgxMCBcdWQ1NThcdWIwOTgoJnF1b3Q7LiZxdW90OylcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL2Rpdj5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBcdWQ1NzRcdWIyZjkgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YWRlMFx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTc0ICZxdW90O3llcyZxdW90O1x1Yjk3YywgXHVjNTQ0XHViMmM4XHViYTc0ICZxdW90O25vJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+N1x1YmM4OFx1YzlmOFx1Yzc1OCAmcXVvdDsgLiZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVhZDA0XHVkNjM4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1YWRlMFx1ZDYxNVx1YzdhMVx1ZDc4YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVhYzA0XHVjOGZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0OTQ5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEJhbGFuY2Ugb2YgdGhlIFdvcmxkIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgd29ybGQgc2hvdWxkIGJlIGZpbmVseSBiYWxhbmNlZC4gUG9zaXRpdmUgdnMuIG5lZ2F0aXZlLCBsaWdodCB2cy4gc2hhZG93LCBhbmQgbGVmdCB2cy4gcmlnaHQgYnJhY2tldHMuIFlvdXIgbWlzc2lvbiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBqdWRnZXMgd2hldGhlciBhIHN0cmluZyBpcyBiYWxhbmNlZCB3aXRoIHJlc3BlY3QgdG8gYnJhY2tldHMgc28gdGhhdCB3ZSBjYW4gb2JzZXJ2ZSB0aGUgYmFsYW5jZSBvZiB0aGUgd29ybGQuPFwvcD5cclxuXHJcbjxwPkEgc3RyaW5nIHRoYXQgd2lsbCBiZSBnaXZlbiB0byB0aGUgcHJvZ3JhbSBtYXkgaGF2ZSB0d28ga2luZHMgb2YgYnJhY2tldHMsIHJvdW5kICgmbGRxdW87KCApJnJkcXVvOykgYW5kIHNxdWFyZSAoJmxkcXVvO1sgXSZyZHF1bzspLiBBIHN0cmluZyBpcyBiYWxhbmNlZCBpZiBhbmQgb25seSBpZiB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnMgaG9sZC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Gb3IgZXZlcnkgbGVmdCByb3VuZCBicmFja2V0ICgmbGRxdW87KCZyZHF1bzspLCB0aGVyZSBpcyBhIGNvcnJlc3BvbmRpbmcgcmlnaHQgcm91bmQgYnJhY2tldCAoJmxkcXVvOykmcmRxdW87KSBpbiB0aGUgZm9sbG93aW5nIHBhcnQgb2YgdGhlIHN0cmluZy48XC9saT5cclxuXHQ8bGk+Rm9yIGV2ZXJ5IGxlZnQgc3F1YXJlIGJyYWNrZXQgKCZsZHF1bztbJnJkcXVvOyksIHRoZXJlIGlzIGEgY29ycmVzcG9uZGluZyByaWdodCBzcXVhcmUgYnJhY2tldCAoJmxkcXVvO10mcmRxdW87KSBpbiB0aGUgZm9sbG93aW5nIHBhcnQgb2YgdGhlIHN0cmluZy48XC9saT5cclxuXHQ8bGk+Rm9yIGV2ZXJ5IHJpZ2h0IGJyYWNrZXQsIHRoZXJlIGlzIGEgbGVmdCBicmFja2V0IGNvcnJlc3BvbmRpbmcgdG8gaXQuPFwvbGk+XHJcblx0PGxpPkNvcnJlc3BvbmRlbmNlcyBvZiBicmFja2V0cyBoYXZlIHRvIGJlIG9uZSB0byBvbmUsIHRoYXQgaXMsIGEgc2luZ2xlIGJyYWNrZXQgbmV2ZXIgY29ycmVzcG9uZHMgdG8gdHdvIG9yIG1vcmUgYnJhY2tldHMuPFwvbGk+XHJcblx0PGxpPkZvciBldmVyeSBwYWlyIG9mIGNvcnJlc3BvbmRpbmcgbGVmdCBhbmQgcmlnaHQgYnJhY2tldHMsIHRoZSBzdWJzdHJpbmcgYmV0d2VlbiB0aGVtIGlzIGJhbGFuY2VkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Ygb25lIG9yIG1vcmUgbGluZXMsIGVhY2ggb2Ygd2hpY2ggYmVpbmcgYSBkYXRhc2V0LiBBIGRhdGFzZXQgaXMgYSBzdHJpbmcgdGhhdCBjb25zaXN0cyBvZiBFbmdsaXNoIGFscGhhYmV0cywgc3BhY2UgY2hhcmFjdGVycywgYW5kIHR3byBraW5kcyBvZiBicmFja2V0cywgcm91bmQgKCZsZHF1bzsoICkmcmRxdW87KSBhbmQgc3F1YXJlICgmbGRxdW87WyBdJnJkcXVvOyksIHRlcm1pbmF0ZWQgYnkgYSBwZXJpb2QuIFlvdSBjYW4gYXNzdW1lIHRoYXQgZXZlcnkgbGluZSBoYXMgMTAwIGNoYXJhY3RlcnMgb3IgbGVzcy4gVGhlIGxpbmUgZm9ybWVkIGJ5IGEgc2luZ2xlIHBlcmlvZCBpbmRpY2F0ZXMgdGhlIGVuZCBvZiB0aGUgaW5wdXQsIHdoaWNoIGlzIG5vdCBhIGRhdGFzZXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgb3V0cHV0ICZsZHF1bzt5ZXMmcmRxdW87IGlmIHRoZSBzdHJpbmcgaXMgYmFsYW5jZWQsIG9yICZsZHF1bztubyZyZHF1bzsgb3RoZXJ3aXNlLCBpbiBhIGxpbmUuIFRoZXJlIG1heSBub3QgYmUgYW55IGV4dHJhIGNoYXJhY3RlcnMgaW4gdGhlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- 0. 주어진 문자열을 하나씩 탐색하며 괄호는 스텍에 저장한다.
- 1. )나 }가 나온다면 이를 스택 내에 가장 마지막에 있는 값과 비교해 매칭이 되는지 확인한다.
- 2. 매칭이 된다면 pass, 매칭이 안된다면 탐색을 중단하고 no를 출력한다.
- 3. 모든 탐색이 끝나고, 스택에 값이 없다면 yes를 출력한다.

코드

# https://www.acmicpc.net/problem/4949
# 접근 방법
# 0. 주어진 문자열을 하나씩 탐색하며 괄호는 스텍에 저장한다.
# 1. )나 }가 나온다면 이를 스택 내에 가장 마지막에 있는 값과 비교해 매칭이 되는지 확인한다.
# 2. 매칭이 된다면 pass, 매칭이 안된다면 탐색을 중단하고 no를 출력한다.
# 3. 모든 탐색이 끝나고, 스택에 값이 없다면 yes를 출력한다.
while True:
    s = input()
    if s == ".":
        break
    stack = []
    is_wrong = False
    for x in s:
        if x == "(" or x == "[":
            stack.append(x)
        elif x == ")":
            if stack and stack[-1] == "(":
                stack.pop()
            else:
                is_wrong = True
                break
        elif x == "]":
            if stack and stack[-1] == "[":
                stack.pop()
            else:
                is_wrong = True
                break
    if is_wrong or stack:
        print('no')
    else:
        print('yes')